문제

Intuition

가장 큰 문제는 배열 안에 최소값에 대해서 어떻게 해야할까이다.
최소값과 상관 없이 무조건 1로 시작한다고 하자.
[3,2,1,0] 은 그러면
[1, 0, -1, -2]를 갖게 된다. 모두 양수의 캔디를 갖게 만들면
1 - 3 + 12 = 10이 된다.

다른예로
[3, 2, 3, 1, 4]는
[1, 0, 1, 0, 1]이 되므로 0보다 크게 만들면
3 + 5 = 8이 될테다.

그러므로 O(n)으로 이웃들간의 높이 차이를 확인하고 최솟값을 기억한 후 최솟값이 0보다 크면 안 더해줘도 되지만 1보다 작으면 0보다 크게 더해주면 될 듯 하다.

First Attempt

class Solution {
    public int candy(int[] ratings) {
        int minimum = 1;
        int numOfCandies = 1; 
        int previousCandy = 1;

        for (int i = 1; i < ratings.length; i++) {
            int currentCandy;
            if (ratings[i] > ratings[i - 1]) {
                currentCandy = previousCandy + 1; 
            } else if (ratings[i] < ratings[i - 1]) {
                currentCandy = previousCandy - 1;
                if (currentCandy < minimum) {
                    minimum = currentCandy;
                }
            } else {
                currentCandy = previousCandy
            }

            numOfCandies += currentCandy;
            previousCandy = currentCandy;
        }

        if (minimum <= 0) {
            numOfCandies += (1 - minimum) * ratings.length;
        }

        return numOfCandies;
    }
}

이렇게 하면 말이 될 줄 알았다. 그런데 왠걸, neighbors는 주변인들이었고 "Children with a higher rating get more candies than their neighbors." 이라는 뜻은 주변인들이 같다면 하나 덜 받아도 된다는 뜻이다 (이게 뭔 개소리지)

아무튼 이렇게 해서 틀렸다.

Second Attempt

댓글을 보니 1로 Initialize하고 왼쪽으로 한번, 오른쪽으로 한번 iterate하라고 한다.
[1, 2, 2, 1]은
[1, 1, 1, 1]에서

candies[i]와 candies[i - 1]을 비교하면
왼쪽: [1, 2, 1, 1]
오른쪽: [1, 2, 2, 1]

[1, 0, 2]은
[1, 1, 1]에서

[1, 1, 2]가 되고
[2, 1, 2]가 된다.

[1, 2, 3, 1, 1]이 있을때엔
왼쪽: [1, 2, 3, 1, 1]
오른쪽: [1, 1, 2, 2, 1]이 되면 안되기에
Math.max()를 오른쪽에서 갈때에 적용해준다.

답

class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length]; 
        Arrays.fill(candies, 1); 

        for (int i = 0; i < candies.length - 1; i++) {
            if (ratings[i + 1] > ratings[i]) {
                candies[i + 1] = candies[i] + 1;
            }
        }

        for (int i = candies.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i + 1] + 1, candies[i]);
            }
        }

        return Arrays.stream(candies).sum(); 
    }
}

// [1, 2, 1, 1, 1]
// [1, 2, 1, 2, 1]