[LEET CODE 150] - 135 Candy

LeetCode의135번인 "Candy" 문제를 풀어봤다.

2-pass + 그리디 알고리즘을 활용한 문제풀이다.

 

문제요약

아이들이 일렬로 있고 ratings[i]가 주어진다.

 

규칙:

1. 모든 아이는 최소 1개의 사탕을 받는다.

2. 인접한 두 아이 중 평점이 더 높은 아이는 사탕도 더 많이 받아야 한다.

이 규칙을 만족하는 사탕의 최소 총합을 구하는 문제다.

---

아이디어

한번에 양쪽 조건을 동시에 만족시키기 어렵기 때문에 2번 스캔 한다.

• 왼쪽 → 오른쪽 Pass:
  • ratings[i] > ratings[i-1] 이면 candies[i] = candies[i-1] + 1 →  "왼쪽 이웃보다 평점 높으면 더많이" 조건 만족
• 오른쪽 → 왼쪽 Pass:
  • ratings[i] > ratings[i+1] 이면 candies[i]가 최소 candies[i+1] +1 은 되어야 한다. →  오른쪽 이웃보다 평점 높으면 더많이 조건까지 보정

여기서 중요한 점은 두번째 pass는 첫 pass에서 만든 값을 깨지 않으면서 오른쪽 조건을 만족시켜야 해서 max()를 쓴다.

---

정답 코드(Python)

class Solution:
    def candy(self, ratings: List[int]) -> int:
        arr = [1] * len(ratings)

        for i in range(1, len(ratings)):
            if ratings[i - 1] < ratings[i]:
                arr[i] = arr[i - 1] + 1

        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings [i + 1]:
                arr[i] = max(arr[i], arr[i + 1] + 1)

        return sum(arr)

---

코드 해석

1.모든 아이에게 사탕 최소 1개를 준상태로 시작한다

arr = [1] * len(ratings)

 

2.왼쪽에서 오른쪽 pass : ratings[i]가 왼쪽보다 크면,사탕도 반드시 더 많아야 하고 그래서 arr[i] = arr[i-1] + 1로 최소 조건을 맞춘다. 이 pass가 끝나면 왼쪽 조건은 전부 만족한다.

for i in range(1, len(ratings)):
	if ratings[i - 1] < ratings[i]:
    	arr[i] = arr[i - 1] + 1

 

3.오른쪽에서 왼쪽 pass: 이번에는 오른쪽 이웃과 비교하고 ratings[i] 가 오른쪽보다 크면 arr[i] >= arr[i+1] +1 이어야 한다. 근데 arr[i]는 이미 왼쪽 pass에서 커져 있을수 있다. 그값을 줄이면 왼쪽 조건이 깨질수도 있기 때문에, 현재값(arr[i])과 오른쪽 요구치(arr[i + 1] + 1)중 큰 값을 선택한다. arr[i] = max(arr[i], arr[i+1] + 1)

 

3-1 : 조건을 만족하는 최소 사탕 배분이 arr에 들어 있으니 총합 반환.

for i in range(len(ratings) -2, -1, -1):
	if ratings[i] > ratings[i + 1]:
    	arr[i] = max(arr[i], arr[i + 1] + 1)
        
        
return sum(arr)

 

정리

왼쪽 증가 조건을 먼저 만족시키고, 오른쪽 증가 조건을 역방향으로 보정한다.

두번째 pass에서는 기존 값을 줄이면 다른 조건이 깨질수 있어 max()로 최소한의 증가만 적용한다.