Leetcode 135 - Candy (Javascript) 1-pass 방식으로 풀기

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

 

문제 난이도는 hard지만 기본 풀이법은 그다지 어렵지 않은 문제라고 생각햇다...

 

초기 풀이법(2-pass)

1. 캔디 배열 1로 초기화 -> 무조건 1개는 받아야함

2. 오른쪽으로 이동하면서 1차순회

3. 다시 왼쪽으로 이동하면서 캔디 개수를 업데이트

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let candies = Array(ratings.length).fill(1)
    for(let i = 0; i < ratings.length -1; i++) {
        if(ratings[i] < ratings[i + 1]&& candies[i + 1] <= candies[i]) {
            candies[i+1] = candies[i] + 1 
        }
    }
    
    for(let i = ratings.length -1; i >0; i--) {
        if(ratings[i] < ratings[i -1] && candies[i - 1] <= candies[i] ){
            candies[i - 1] = candies[i] + 1 
        }
    }
    return candies.reduce((a,b)=> a+b, 0)
};

 

근데 loop를 2번을 한다는게 당연히 마음에 안듬 게다가 시간도 오래 걸렷기에

분명 다른 방법이 있을 것이라 확신했다

하지만 도저히 방법을 떠올릴 수가 없었다.....

 

개선된 풀이 방식(1-pass)

1. 모든 아이에게 1개씩 사탕을 줬다고 가정하고 시작 -> 배열 생성 x

2. 오름차순 구간 → 추가 사탕을 1, 2, 3... 식으로 누적 지급 ->peak 계산

3. 내림차순 구간→ 똑같이 1, 2, 3... 식으로 누적 지급 -> valley 계산

4. 오르막과 내리막이 만나는 꼭짓점(peak, valley)은 중복 계산되므로 더 작은 수 빼야함

 

 

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    const n = ratings.length;
    let candies = n; // 모든 아이에게 1개씩 지급했다고 가정
    let i = 1;

    while (i < n) {
        // 같은 rating이면 조건 없음 → 패스
        if (ratings[i] === ratings[i - 1]) {
            i++;
            continue;
        }

        // 오름차순 처리
        let peak = 0;
        while (i < n && ratings[i] > ratings[i - 1]) {
            peak++;
            candies += peak; // 추가 사탕 지급
            i++;
        }

        // 내림차순 처리
        let valley = 0;
        while (i < n && ratings[i] < ratings[i - 1]) {
            valley++;
            candies += valley;
            i++;
        }

        // 꼭짓점이 peak와 valley에서 중복 계산됨
        candies -= Math.min(peak, valley);
    }

    return candies;
};

 

내가 푼 방식은 easy난이도에 맞는 방식이고...이 방식이 왠지 hard에 적합한 느낌이다

한번만 순회하면 되는 풀이법이라 시간복잡도도 좋고 추가 배열도 사용하지않아 공간복잡도는 당연히 좋다

도대체 이런 방식은 어떻게 생각하는 건지..

 

peak/valley 알고리즘에 대해서 챗지피티한테 물어봄

이 문제는 "오름차순, 내림차순" 흐름이 번갈아 반복된다는 점에서
Peak/Valley 패턴을 활용해 한 번의 순회로 해결할 수 있습니다.

 

은근 이런 문제를 몇번 봣던 것 같은데 잘 기억해둬야겠다.