[LeetCode] Candy

문제링크

Candy - LeetCode

 

모든 아이에게 사탕을 나눠줄 수 있는 사탕의 최소 개수를 구하는 문제
ratings : 순위배열

조건 1. 모든 아이는 최소 1개의 사탕을 받아야한다.
조건 2. 이웃한 아이들끼리는 더 높은 rating을 갖는 아이가 더 많은 캔디를 받을 수 있다.

접근 방법

처음에는 left, right 변수를 만들어 sliding window 방식으로 접근하였다.
하지만 ratings = [3, 2, 1, 2, 3] 같은 부분에서 left와 right의 이동 조건을 만족시키려면 조건이 너무 복잡해졌고

완전 탐색을 앞에서부터 1번, 뒤에서부터 1번 진행하는 방식으로 바꾸었다.

1. ratings 길이의 배열을 만들어 모든 값을 1로 채운다.

let candyArr = new Array(ratings.length).fill(1);​

2. ratings를 앞에서부터 ratings[i -1] < ratings[i] 일 경우를 처리한다.
( ratings = [5, 3, 1, 2, 3] => candyArr = [1, 1, 1, 2, 3] )

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

3. ratings를 뒤에서부터 ratings[i] > ratings[i + 1] 일 경우를 처리한다.
( ratings = [5, 3, 1, 2, 3] => candyArr = [1, 1, 1, 2, 3] => candyArr = [3, 2, 1, 2, 3] )

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

 

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let output = 0;
    let candyArr = new Array(ratings.length).fill(1);
    
    for(let i = 1; i < ratings.length; i++){
        if(ratings[i-1] < ratings[i]) candyArr[i] = candyArr[i-1] + 1;
    }
    
    for(let i = ratings.length - 2; i >= 0; i--){
        if(ratings[i] > ratings[i+1]){
            candyArr[i] = Math.max(candyArr[i], candyArr[i+1] + 1)
        }
    }
    
    output = candyArr.reduce((acc, cur) => acc + cur)
    return output
};