[LeetCode] 135. Candy

문제 출처: https://leetcode.com/problems/candy/

Candy - LeetCode

 

문제

n명의 아이들이 줄 서 있다. 각 아이들 마다 점수가 매겨져 정수 배열 ratings로 표현된다.

다음의 규칙에 따라서 이 아이들에게 사탕을 나눠주려 한다:

• 각 아이는 최소 1개의 사탕을 가져야 한다.
• 아이들은 이웃 아이보다 점수가 높다면 더 많은 사탕을 가져야 한다.

 

아이들에게 사탕을 분배하기 위해 필요한 최소 사탕 수 를 반환하라.

 

예제

Input: ratings = [1,0,2]
Output: 5

Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Input: ratings = [1,2,2]
Output: 4

Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

 

풀이

아이들에게 줄 사탕의 수를 저장하는 배열 numOfCandy가 있다고 하자.

 

임의의 i번째 아이에게 줄 사탕의 수를 특정하기 위해서는 numOfCandy[i-1]과 numOfCandy[i+1]의 값을 알아야 한다. 이 값들을 알고 있다면, max(ratings[i-1], ratings[i+1])와 ratings[i] 사이의 관계를 통해 numOfCandy[i]를 특정할 수 있다.

 

문제는 numOfCandy[i-1]과 numOfCandy[i+1]의 값을 알기 위해서는 numOfCandy[i]의 값이 필요하다는 점이다.

 

그래서 이 점을 파훼하기 위해서, 이웃 양쪽을 한 번에 고려하는 것이 아닌, 한쪽의 이웃으로만 사탕 수를 계산하고 나중에 이를 취합하는 방법을 생각해보았다.

 

예를 들어, ratings = [1, 0, 2]라고 하면, 다음과 같이 numOfCandy를 두 가지로 나눌 수 있다.

• 만약 i번째 아이의 왼쪽 아이의 점수만을 고려한다면, numOfCandy_left = [1, 1, 2]
• 만약 i번째 아이의 오른쪽 아이의 점수만을 고려한다면, numOfCandy_right = [2, 1, 1]

 

이 두 배열의 취합은 각 인덱스마다 최댓값을 선택하는 것이다. 위 예제에서 최종 결과물은 numOfCandy = [2, 1, 2] 가 된다.

 

이 과정을 코드로 작성하면 다음과 같다.

var candy = function(ratings) {
    const N = ratings.length;

    const numOfCandy_left = new Array(N).fill(0);
    for (let i = 1; i < N; i++) {
        if (ratings[i-1] < ratings[i]) { numOfCandy_left[i] = numOfCandy_left[i-1] + 1; }
    }

    const numOfCandy_right = new Array(N).fill(0);
    for (let i = N-2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) { numOfCandy_right[i] = numOfCandy_right[i+1] + 1; }
    }

    const numOfCandy = new Array(N);
    for (let i = 0; i < N; i++) {
        numOfCandy[i] = Math.max(numOfCandy_left[i], numOfCandy_right[i]);
    }

    return numOfCandy.reduce((acc, val) => acc + val);
}

 

Github: 135.js

opwe37/Algorithm-Study