Today's Challenge

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

Candy - LeetCode

일단 난이도가 hard라 ㅎㄷㄷ 한 마음으로 풀기 시작.
뭔가 연쇄효과가 일어날 것도 같고, 점화식으로 풀어야 될 것 같은 생각이 듦.

공식 솔루션을 봤더니 2-way라는 방법으로 풀 수 있음.
왼쪽에서 오른쪽으로 순회하면서 숫자를 계산하고
다시 오른쪽에서 왼쪽으로 순회하면서 숫자를 계산한 다음에 max를 구한 뒤, 총합을 계산하면 됨.

class Solution:
    def candy(self, ratings: List[int]) -> int:
        l = len(ratings)
        lr, rl, res = [1] * l, [1] * l, [1] * l
        for i in range(1, l):
            if ratings[i-1] < ratings[i]:
                lr[i] = lr[i-1] + 1
            if ratings[l-i] < ratings[l-i-1]:
                rl[l-i-1] = rl[l-i] + 1
        for i in range(l):
            res[i] = max(lr[i], rl[i])
        return sum(res)