Candy

[hsskey]

문제 설명 | Candy

📝 제약조건

• n == ratings.length
• 1 <= n <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

💡 예시

• Input: ratings = [1,0,2]

  • Output: 5
  • 설명: 첫 번째, 두 번째, 세 번째 아이에게 각각 2, 1, 2개의 사탕을 나눠줌

• Input: ratings = [1,2,2]

  • Output: 4
  • 설명: 첫 번째, 두 번째, 세 번째 아이에게 각각 1, 2, 1개의 사탕을 나눠줌. 세 번째 아이는 위의 두 조건을 만족하기 때문에 1개의 사탕을 받음

문제 해결 과정

Step 1: 문제 이해하기

• 작은 예시로 문제 이해하기
  • 예시 1: [1,0,2] → 결과 5
    • 첫 번째 아이(1)는 두 번째 아이(0)보다 높은 평가를 받았으므로 더 많은 사탕을 받아야 함
    • 세 번째 아이(2)는 두 번째 아이(0)보다 높은 평가를 받았으므로 더 많은 사탕을 받아야 함
    • 최소 사탕 개수: [2,1,2] → 총 5개
  • 예시 2: [1,2,2] → 결과 4
    • 두 번째 아이(2)는 첫 번째 아이(1)보다 높은 평가를 받았으므로 더 많은 사탕을 받아야 함
    • 세 번째 아이(2)는 인접한 아이와 평가가 같아 최소 1개의 사탕을 받음
    • 최소 사탕 개수: [1,2,1] → 총 4개

Step 2: 접근 방법

• 직관적으로 생각하기
  • 모든 아이에게 우선 1개의 사탕을 줌
  • 양쪽 이웃과의 관계를 고려해야 함
  • 한 방향으로만 비교하면 양쪽 이웃과의 관계를 모두 고려할 수 없음
• 그리디 알고리즘 적용
  • 양방향으로 탐색하여 최소 사탕 개수 계산
  • 왼쪽→오른쪽 패스: 현재 아이의 평가가 왼쪽 아이보다 높으면 왼쪽 아이보다 1개 더 많은 사탕을 줌
  • 오른쪽→왼쪽 패스: 현재 아이의 평가가 오른쪽 아이보다 높으면 오른쪽 아이보다 1개 더 많은 사탕을 줌

Step 3: 코드 설계

1. 사탕 배열 초기화: 모든 아이에게 1개의 사탕을 할당
2. 왼쪽→오른쪽 패스:
   • 현재 아이의 평가가 왼쪽 아이보다 높으면 왼쪽 아이의 사탕 + 1
3. 오른쪽→왼쪽 패스:
   • 현재 아이의 평가가 오른쪽 아이보다 높으면 max(현재 사탕, 오른쪽 아이의 사탕 + 1)
4. 모든 사탕의 합 반환

Step 4: 코드 구현

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1); // 모든 아이에게 일단 1개씩 사탕 할당
    
    // 왼쪽에서 오른쪽으로 순회
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    
    // 오른쪽에서 왼쪽으로 순회
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            // 현재 값과 (오른쪽 아이 사탕 + 1) 중 더 큰 값으로 설정
            candies[i] = Math.max(candies[i], candies[i+1] + 1);
        }
    }
    
    // 모든 사탕의 합계를 반환
    return candies.reduce((sum, val) => sum + val, 0);
};