[알고리즘] Candy

포인트

• 그리디 알고리즘을 잘 알고 있는가? 
• 처음에는 브루트포스 접근으로 생각을 하였다. 하지만, 제한 조건이 2*10^4 이었고 아룰 n^2 이상으로 넘어갈 경우는 제대로 해결하지 못할 것으로 예상을 하여 다른 방식으로 해결하였다.
• 바로 그리디 방식으로 해결을 하는 것이다. for loop를 같은 깊이에서 여러 번 함으로 최대 O(n) 임으로 제한 시간안에 만족할 것으로 판단하였다.

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

 

python

class Solution:
    def candy(self, ratings: List[int]) -> int:
        left_right = [1] * len(ratings)
        right_left = [1] * len(ratings)
        sum = 0
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                left_right[i] = left_right[i - 1] + 1
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                right_left[i] = right_left[i + 1] + 1
        for i in range(len(ratings)):
            sum += max(left_right[i], right_left[i])