leetcode hard : Candy

https://leetcode.com/problems/candy/description/

Candy - LeetCode

 

최근 봤던 문제중에 배분과 관련된 문제가 있었는데 그게 그래프문제였어서

distribution이라는 단어를 보자마자 혹시 그래프? 했는데 아니었다 ㅋㅋ

이 문제는 그리디 문제인데

그리디문제는 사실 솔루션 발상까지의 어떤 명확한 발상과정이 있다기보다는

어? 하고 뚝 떠오르는 경우가 많은거같다.

솔루션은 생각보다 간단하다.

1. 아이들에게 줄 캔디 개수 배열을 1로 초기화한다.

2. 왼쪽부터 오른쪽으로 스캔하면서 나보다 오른쪽에 있는애가 레이팅이 높으면 반드시 캔디를 더 많이 가질수있게 한다.

3. 오른쪽에서 왼쪽으로 스캔하면서 나보다 왼쪽에 있는애가 레이팅이 높으면 반드시 캔디를 더 많이 가질수있게 한다.

그래서 2번과 3번을 어떻게 하느냐가 궁금할텐데, 코드를보면 의문이 금방 풀린다.

 

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

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

max부분이 좀 궁금할수도 있는데, 한 가지 고려해야될 부분이 있어서 그렇다.

left -> right 스캔을 한 번 한 상태기 때문에 i가 i-1보다 랭킹이 높으면 캔디개수가 1 더 많을것이다.

이럴경우는 candies[i]가 더 낮아지면 안된다.

근데 만약 candies[i + 1] + 1이 candies[i]보다 작으면? 이미 candies[i] > candies[i+1] 조건도 만족될뿐더러 첫번째 스캔에서 만들어놓은 left < right 정합성도 깨면 안되니까 candies[i]를 그대로 냅둬야 할 것이다. 그래서 둘중에 더 큰값을 선택한다는 의미로 max를 쓴것이다.

 

복잡도

시간 O(N)

공간 O(1)