[LeetCode] 135. Candy

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candy = new int[n];

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->{
            return Integer.compare(a[1], b[1]);
        });

        for (int i = 0; i < n; i++) {
            int[] tmp = new int[]{i, ratings[i]};
            pq.add(tmp);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) { 
            int[] tmp = pq.poll();
            int idx = tmp[0];
            int v = tmp[1];
            int l = 1;
            int r = 1;
            if (idx != 0 && ratings[idx-1] != v && candy[idx-1] != 0) {
                l = candy[idx-1] + 1;
            }
            if (idx != n-1 && ratings[idx+1] != v && candy[idx+1] != 0) {
                r = candy[idx+1] + 1;
            }

            candy[idx] = Math.max(l, r);
            ans += candy[idx];
        }

        return ans;
    }
}

풀이

우선순위 큐를  사용하여 점수가 낮은 친구부터 사탕을 준다.
x 번째 친구에게 사탕을 줄때 그 친구 양옆으로 사탕을 받은 친구가 있는지 확인한다. 사탕을 받은 친구가 있다면  x번째 친구는 점수가 더 높기 때문에 사탕을 한개 더 준다.(우선순위 큐)
단, 점수가 같을 수도 있다. 그런경우는 사탕을 1개만 줘도된다.

후기

난이도가 하드였어서 분명 최적화에 걸리겠다 싶었는데 통과됐음..