135. Candy

 

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)  # 아이들의 수
        res = [1] * n  # 각 아이에게 최소 1개의 사탕을 할당

        # 1단계: 왼쪽에서 오른쪽으로 순회하며 사탕 배분
        for i in range(1, n):  # 두 번째 아이부터 시작 (인덱스 1)
            if ratings[i - 1] < ratings[i]:  # 현재 아이의 점수가 왼쪽 아이보다 높다면
                res[i] = res[i - 1] + 1  # 왼쪽 아이보다 1개 더 많은 사탕을 줌

        # 2단계: 오른쪽에서 왼쪽으로 순회하며 사탕 배분 수정
        for i in range(n - 2, -1, -1):  # 마지막-1 번째 아이부터 시작 (인덱스 n-2)
            if ratings[i] > ratings[i + 1]:  # 현재 아이의 점수가 오른쪽 아이보다 높다면
                # 현재 할당된 사탕 수와 (오른쪽 아이 사탕 + 1) 중 더 큰 값을 선택
                res[i] = max(res[i], res[i + 1] + 1)

        # 3단계: 전체 사탕 개수 합산하여 반환
        return sum(res)  # 모든 아이에게 할당된 사탕의 총합 반환

135. Candy

 

https://youtu.be/1IzCRCcK17A?si=XL6z4evzdKARdQ3h

 

주요 설명

1. 왼쪽에서 오른쪽으로 순회

• 목적: 왼쪽 아이의 점수를 기준으로 현재 아이에게 필요한 최소 사탕을 할당.
• 각 아이의 점수가 왼쪽 아이보다 높으면, 왼쪽 아이보다 1개 더 많은 사탕을 줌.
• res 배열을 업데이트하여 현재까지 계산된 사탕 수를 저장.

2. 오른쪽에서 왼쪽으로 순회

• 목적: 오른쪽 아이의 점수를 기준으로 현재 아이에게 필요한 사탕 개수를 수정.
• 오른쪽 아이보다 점수가 높은 경우, 기존 사탕 개수(res[i])와 오른쪽 아이 사탕 + 1(res[i + 1] + 1) 중 더 큰 값을 선택.
• 이 단계는 왼쪽에서 오른쪽 단계에서 놓친 "오른쪽 기준 조건"을 보완.

3. 사탕 개수 합산

• res 배열에 저장된 각 아이의 사탕 수를 합산하여 반환.
• 이 배열은 모든 조건(왼쪽 기준, 오른쪽 기준)을 만족한 최소 사탕 분배 결과를 나타냄.