문제 소개
N명의 아이들이 한 줄로 서 있고, 각 아이에게는 고유한 평점(rating) 값이 부여되어 있다고 가정해 보겠습니다. 우리는 다음 두 가지 조건을 만족하면서 아이들에게 사탕을 나누어 주어야 합니다.
- 모든 아이는 최소한 사탕 한 개를 받아야 합니다.
- 평점이 더 높은 아이는 자신의 양옆에 있는 이웃 아이들보다 많은 사탕을 받아야 합니다.
이러한 조건을 만족하면서 나누어 주어야 할 사탕의 최소 개수를 구하는 것이 이 문제의 목표입니다.
예시
입력이 [1, 1, 3]이라면 출력은 4가 됩니다. 세 명의 아이는 각각 1개, 1개, 2개의 사탕을 받게 됩니다. 마지막 아이의 평점(3)이 앞의 두 아이(1)보다 높기 때문에, 이 아이는 이웃보다 많은 사탕을 받아야 하므로 2개를 지급하는 것이 최소가 됩니다.
해결 접근 방법
이 문제는 양방향 순회(Two-pass) 그리디 알고리즘으로 효율적으로 해결할 수 있습니다. 단계별로 살펴보겠습니다.
- n을 ratings 배열의 크기로 설정하고, 크기가 n인 dp 배열을 생성하여 모든 값을 1로 초기화합니다. (조건상 모든 아이는 최소 1개의 사탕을 받습니다.)
- 결과를 저장할 변수 ret을 0으로 초기화합니다.
- i를 1부터 n-1까지 왼쪽에서 오른쪽으로 순회하면서, 만약 ratings[i] > ratings[i-1]이라면 dp[i] = dp[i-1] + 1로 갱신합니다. 이렇게 하면 왼쪽 이웃보다 평점이 높은 아이가 더 많은 사탕을 받게 됩니다.
- i를 n-2부터 0까지 오른쪽에서 왼쪽으로 역순 순회하면서, 만약 ratings[i] > ratings[i+1]이라면 dp[i] = max(dp[i], dp[i+1] + 1)로 갱신합니다. 기존 값과 비교하여 더 큰 값을 유지함으로써 양방향 조건을 모두 만족시킵니다.
- ret에 dp 배열의 모든 요소의 합을 저장합니다.
- ret을 반환합니다.
두 번의 순회를 거치면 각 위치에서 왼쪽 조건과 오른쪽 조건이 동시에 충족되므로, 전체 사탕 개수가 최소화됩니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n)입니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
vector <int> dp(n, 1);
int ret = 0;
for(int i = 1; i < n; i++){
if(ratings[i] > ratings[i - 1]){
dp[i] = dp[i - 1] + 1;
}
}
for(int i = n - 2; i >= 0; i--){
if(ratings[i] > ratings[i + 1]){
dp[i] = max(dp[i], dp[i + 1] + 1);
}
}
for(int i = 0; i < n; i+=1){
ret += dp[i];
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,1,3};
cout << (ob.candy(v));
}입력
[1,1,3]
출력
4
마무리
사탕 분배 문제는 그리디 알고리즘의 대표적인 유형으로, 코딩 테스트와 면접에서 자주 등장하는 문제입니다. 핵심은 왼쪽과 오른쪽을 각각 한 번씩 순회하며 인접한 아이들 간의 평점 비교 조건을 독립적으로 처리하는 것입니다. 이 방식을 익혀두면 비슷한 패턴의 배열 순회 문제를 해결할 때 큰 도움이 됩니다.