leetcode 135, Candy(java)

문제 설명

n 명의 아이들이 서 있다. 각 아이들은 정수로 된 ratings을 부여받는다. 이때 아래의 요청에 따라 아이들에게 사탕을 나누어 준다. 

각 아이들은 적어도 하나의 사탕을 가지고 있어야 한다.

그들의 이웃보다 더 rating이 크다면 해당 아이는 더 많은 사탕을 가져야 한다.

아이들에게 나눠줄 수 있는 사탕의 최소 개수를 구하여라.

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

Candy - LeetCode

문제 풀이

문제에서 나온 예로 더 자세하게 설명을 해보자.

ratings가 [1, 0, 2] 이렇게 되어 있다고 하면 각 아이들이 갖는 사탕의 수는 2, 1, 2가 된다. 그 이유는 첫 번째 아이의 경우 두 번째 아이보다 rating이 높으니 2를 갖고 두 번째 아이는 양 옆의 어떤 아이보다 rating이 적으니 1을 갖는다. 그리고 세 번째 아이는 두 번째 아이보다 rating이 높으니 두 번째 아이보다 더 많은 사탕인 2를 갖는다.

 

ratings가 [1, 2, 2]로 주어지면 사탕을 1, 2, 1로 나눠줄 수 있다. 여기서 세 번째 아이에게 의문을 가질 수 있는데, 비록 세 번째 아이는 두 번째 아이보다 rating이 적지는 않지만 크지도 않으므로 두 번째 조건에서 탈락하게 되는 것이다.

 

참고로 이웃 중 rating이 적은 한 명 보다는 사탕을 더 많이 줘야 한다. 예를 들어서 [87, 87, 2, 1] 로 ratings가 주어진다고 해보자. 그러면 정답은 [1, 3, 2, 1] 로 7이 된다.

일단 첫 번째 아이는 이웃인 두 번째 아이와 비교했을 때 rating이 같으므로 사탕을 1개 갖는다. 그리고 두 번째 아이는 이웃인 첫 번째 아이와는 rating이 같지만 또 다른 이웃인 세 번째 아이보다 rating이 크므로 사탕을 2개... 가질까? 아니, 두 번째 아이는 사탕을 3개 갖는다. 왜냐하면 세 번째 아이의 오른쪽 이웃의 rating이 1이라 세 번째 아이의 rating이 더 크므로 세 번째 아이는 사탕을 2개 갖기 때문이다. 그러므로 두 번째 아이는 세 번째 아이가 가진 사탕의 수 보다 더 많이 가져야 하므로 적어도 3개를 받아야 하는 것이다.

 

dp... 가 생각나지 않는가? 나는 dp를 이용해 이웃의 rating보다 현재의 rating이 더 크면 해당 이웃의 사탕 수에 1을 더하는 방식으로 풀었다.

 

1. 모든 dp에 1 넣어주기

모든 아이들은 적어도 1개의 사탕이 필요하다고 하였으니 dp에 1을 넣어준다.

        for (int i=0; i<dp.length; i++) {
            dp[i] = 1;
        }

2. index를 1부터 시작하여 현재 index의 왼쪽을 확인하기

만일 index-1(현재 index의 왼쪽)의 rating이 더 작다면 왼쪽의 dp 값이 1을 더한 값을 현재의 dp index에 넣어준다.

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

3. index를 n-2부터 시작하여 현재 index의 오른쪽을 확인하기

현재 index의 +1인 오른쪽 값을 확인해서 현재 index의 rating이 더 크다면 어떻게 할 것인가. 단순히 index+1의 dp 값에 1을 더해줄까? 아니, 우리는 이미 1부터 index의 왼쪽을 보면서 나의 왼쪽 이웃을 확인해줬다(사탕의 최솟값을 구하는 문제라는 걸 잊지 말자). 그러므로 이때는 rating이 큰 것 뿐만 아니라 현재 index의 dp 값이 index+1의 dp 값보다 작거나 같으면 index+1의 dp에 1을 더한 값을 넣어줘야 한다.

 

위에서 든 예시 [87, 87, 2, 1]이 바로 여기에 해당한다.

2번을 진행하였다면 dp의 값은 [1, 2, 2, 1]이 될 것이다. 여기서 3번을 진행한다면 두 번째 index의 rating이 세 번째 rating보다 크고 dp는 서로 같으니 두 번째 index의 dp 값은 세 번째 index의 dp 값에다 1을 더한 값인 3이 될 것이다.

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

4. dp를 전부 더해 answer을 구한 다음 return

        for (int d : dp) {
            answer += d;
        }

        return answer;

코드

java

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

        for (int i=0; i<dp.length; i++) {
            dp[i] = 1;
        }

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

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

        for (int d : dp) {
            answer += d;
        }

        return answer;
    }
}