LeetCode 135. Candy

문제 링크

---

문제 해석

아이들이 일렬로 서 있고, 각 아이는 ratings 배열로 평점를 가진다.
사탕을 나눠줄 때 다음의 조건을 만족해야 한다.

1. 모든 아이는 최소 1개의 사탕을 받아야 한다.
2. 이웃한 아이보다 평점이 높은 경우, 그 아이는 더 많은 사탕을 받아야 한다.

예제 분석

ratings = [1, 2, 2]

해당 예제에서 가장 헷갈렸던 부분은 왜 정답이 [1, 2, 2]가 아닌 [1, 2, 1]인지였다.

조건을 다시 보면 평점이 더 높은 경우에만 사탕을 더 많이 받으면 되므로 평점이 같으면 더 많이 줄 필요가 없다. 문제의 조건을 만족하는 사탕의 최소 개수를 구하는 문제이므로 평점이 높은 경우만 따지면 된다!

코드 구현

우선 모든 아이가 최소 1개의 사탕을 가지므로 길이가 ratings의 길이와 같은 배열을 1로 채운다.

const n = ratings.length;
const candies = new Array(n).fill(1);

그리고 왼쪽 → 오른쪽으로 순회하며 현재 아이의 평점이 왼쪽보다 높으면 사탕의 수를 1씩 늘린다.

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

그 후 오른쪽 → 왼쪽으로 순회하며 현재 아이의 평점이 오른쪽보다 높으면 기존 값과 오른쪽의 사탕 수에서 1을 더한 값을 비교하여 더 큰 값을 선택한다.

두 수 중에서 더 큰 값을 선택하는 이유는 이미 왼쪽 → 오른쪽을 순회하며 만족한 조건을 오른쪽 → 왼쪽을 순회하며 깨뜨리면 안되기 때문이다! 좌우 이웃과의 조건을 동시에 만족해야 하기 때문에 Math.max를 사용하여 값을 업데이트해준다.

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

최종적으로 구해야 하는 값은 사탕의 총 개수이므로 reduce 메서드를 사용하여 candies 배열의 총합을 구하면 된다.

return candies.reduce((a, b) => a + b, 0);

---

전체 코드

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);

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

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

    return candies.reduce((a, b) => a + b, 0);
};