[LeetCode] 135. Candy

😎풀이

해당 문제는 다음과 같은 절차로 2번 전체 순회하여 풀이가 가능하다.

1. 모든 아이에게 최소 1개씩의 사탕을 할당한다.
2. 좌측에서 우측으로 순회하며 i번째 아이가 i - 1번째 아이보다 높은 점수를 갖는 경우 i - 1번째 아이의 사탕보다 1개를 더 부여한다.
3. 우측에서 좌측으로 순회하며 i번째 아이가 i + 1번째 아이보다 높은 점수를 갖는 경우 i + 1번째 아이의 사탕 + 1개 와 i번째 아이의 사탕 중 최댓값을 할당한다. (좌측에서 우측으로 탐색하며 부여된 값과, 우측에서 좌측으로 탐색하며 부여된 값 중 최댓값이 올바른 값)
4. 아이들에게 부여된 사탕의 총 합을 반환한다.

function candy(ratings: number[]): number {
    // 모든 아이들에게 최소 1개의 사탕을 할당하는 배열 생성
    const candies: number[] = new Array(ratings.length).fill(1);
    
    // 왼쪽에서 오른쪽으로 순회하면서 
    // 현재 아이의 rating이 왼쪽 아이보다 높은 경우 처리
    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    
    // 오른쪽에서 왼쪽으로 순회하면서
    // 현재 아이의 rating이 오른쪽 아이보다 높은 경우 처리
    // 이때 이미 할당된 사탕 개수와 비교하여 더 큰 값을 선택
    for (let i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            candies[i] = Math.max(candies[i], candies[i+1] + 1);
        }
    }
    
    // 모든 사탕의 개수를 합산
    return candies.reduce((sum, count) => sum + count, 0);
}