[LeetCode # 135] Candy

n 명의 아이들을 의미하는 정수형 배열이 주어졌을 때, 배열에 저장된 값은 해당 위치에 서 있는 아이의 우선순위를 의미한다. 아이들에게 Candy 를 나눠주고자 하는데 모든 아이들은 최소 1개 이상의 Candy 를 받아야 하고 이웃한 아이보다 우선순위가 높은 아이는 이웃 아이보다 Candy 를 더 받아야 한다. 이 때, 아이들에게 최소한의 갯수로 위 규칙을 만족시키며 Candy 를 분배하는 Candy 의 수를 구하는 문제

 

이 문제는, DP 방식으로 문제를 해결할 수 있었는데 우선 각 아이 별로 왼쪽에 있는 아이보다 많이 받는 경우와 오른쪽에 있는 아이보다 많이 받는 경우를 각각 계산했다. 그 후, 둘 중 더 많은 Candy 를 받는 경우를 계산하면 최소한의 Candy 로 규칙을 만족시키며 분배할 수 있다.

 

예를 들어, ratings 배열이 [1, 0, 2] 로 주어졌을 때 Candy 를 가져가는 개수는 [2, 1, 2] 로 총 5개가 필요하게 된다. 왼쪽에 있는 아이보다 많이 받는 경우를 계산하면 [1, 1, 2] 가 되는데 ratings[1] 은 0 이므로 ratings[0] 보다 작아 더 많이 받을 필요가 없고, ratings[2] 는 2 이고 ratings[1] 은 1 이므로 3번째 아이는 2번째 아이보다 Candy 를 많이 받아야 한다. 반대로 오른쪽에 있는 아이보다 많이 받는 경우는 [2, 1, 1] 이 되는데 ratings[0] 의 오른쪽에 ratings[1] 이 더 작으므로 첫 번째 아이가 Candy 를 많이 받게 된다. 두 경우에서 각 아이가 받는 Candy 의 개수는 최대가 되어야 왼쪽과 오른쪽의 경우를 모두 만족할 수 있으므로 결과적으로 [2, 1, 2] 로 Candy 를 분배하게 된다.

 

위와 같은 풀이로 작성한 코드는 다음과 같다.

 

class Solution {
public:
    int candy(vector<int>& ratings) {
        int sum = 0, n = ratings.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        for (int i = 0; i < n; i++) {
            sum += max(left[i], right[i]);
        }
        return sum;
    }
};