[Leetcode] 135. Candy - JS

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

 

1. 문제 분석

문제분석
------------------
- 줄에 서있는 n명의 아이들이 있다.
- 각각의 아이는 정수 배열 ratings에서 주어진 rating 값을 배정받는다.
- 아이들에게 분배할 최소한의 캔디의 갯수를 반환하라.

- 아래 요구사항에 맞게 아이들에게 캔디를 줘라.
1. 각각의 아이는 최소 1개의 캔디는 가져야한다.
2. 높은 rating을 가진 아이들은 그들의 양 옆의 아이들보다 더 많은 캔디를 가져야한다.

제한조건
------------------
- n == ratings.length
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4

 

2. 접근 방법

접근방법 - Greedy 알고리즘
--------------------
Greedy 알고리즘은 현재 최적으로 보이는 선택을 하는 알고리즘이다.
ratings 배열을 2번 순회하면서 각각의 상황에서 최적의 선택을 하여 문제를 풀어보자.

조건 1. 모든 아이들은 최소 1개의 캔디를 가져야한다.
그러므로 ratings 배열과 동일한 길이를 가진 candies 배열을 1로 초기화 한다.

조건 2. 양옆의 아이들의 rating보다 높으면 캔디를 더 가져야한다.

1번째 인덱스부터 시작하여 마지막까지 ratings를 순회하면서 왼쪽 아이의 rating과 비교하여
현재 아이의 rating이 더 크면 왼쪽 아이의 캔디보다 1개를 더 갖는다.

이를 통해 2번 조건 중 왼쪽의 이웃에 대해서는 충족시킬 수 있다.

그 다음에는 역순으로 ratings를 순회하면서 오른쪽 아이의 rating과 비교하여
현재 아이의 rating이 오른쪽 아이의 rating보다 높으면 캔디를 수정한다.

이 때, 첫번째 순회를 통해 현재 아이의 캔디는 왼쪽 아이와 비교한 결과를 기반으로 캔디를 가지고 있으므로
현재 아이가 가진 캔디와 오른쪽 아이의 캔디 + 1 중에 더 큰 값으로 수정해준다.

마지막으로 candies 배열의 총합을 반환한다.

 

 

3. 코드

var candy = function(ratings) {
    const n = ratings.length;
    const candies = Array.from({length:n}, () => 1);

	// 정방향으로 순회하면서 인덱스 기준 왼쪽 요소와의 rating 비교만 한다.
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1]+1
        }
    }

	// 역방향으로 순회하면서 인덱스 기준 오른쪽 요소와의 rating 비교만 한다.
    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((acc,cur) => acc + cur, 0)
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

문제를 차근히 읽어보고 풀이에 거의 도달한 것 같았지만, 점점 엣지 케이스에 대한 조건이 복잡하고 길어지면서 내가 생각한 방법이 잘못된 접근이라는 것을 알아차리고 풀이를 통해 공부했다.

 

역시 코드 자체는 간결하다. 그런데, 주어진 문제를 해결책을 코드로 나타낼 때 엣지 케이스는 있는지 있다면 어떤 부분을 고려하지 않아서 발생한 엣지 케이스인지 이런 부분을 고려하면서 문제를 해결하는 것이 아직은 어렵게 느껴진다.

 

그래도 해설을 보면서 이해하다보니 프로그래밍은 이렇게 사고를 할 수 있구나라는 것을 점점 깨닫는 것 같아 기분이 좋다.