어떤 아이들에게 쿠키를 나눠 주려고 한다고 가정해 봅시다. 단, 한 명의 아이에게 줄 수 있는 쿠키는 최대 하나뿐입니다. 각 아이 i는 탐욕 계수(greed factor) gi를 가지는데, 이 값은 그 아이가 만족하기 위해 필요한 쿠키의 최소 크기를 의미합니다. 또한 각 쿠키 j는 고유한 크기 sj를 가집니다. sj >= gi를 만족하면 쿠키 j를 아이 i에게 나눠 줄 수 있고, 그 아이는 만족하게 됩니다. 우리의 목표는 만족하는 아이의 수를 최대화하고, 그 최대값을 출력하는 것입니다.
예를 들어 입력이 [1,2]와 [1,2,3]이라면 출력은 2가 됩니다. 두 명의 아이 탐욕 계수는 각각 1과 2이고, 세 개의 쿠키 크기는 모든 아이를 만족시키기에 충분하기 때문에 결과는 2입니다.
해결 접근 방법
이 문제는 대표적인 그리디(Greedy) 알고리즘 문제로, 다음 단계를 따르면 해결할 수 있습니다.
아이들의 탐욕 계수 배열 g를 오름차순으로 정렬합니다.
쿠키 크기 배열 s를 오름차순으로 정렬합니다.
두 포인터 i := 0, j := 0으로 초기화합니다.
(i < g의 크기 && j < s의 크기)인 동안 반복합니다.
g[i] <= s[j]라면 현재 쿠키로 해당 아이를 만족시킬 수 있으므로 i를 1 증가시킵니다.
j는 매번 1 증가시켜 다음 쿠키로 넘어갑니다.
반복이 끝나면 i를 반환합니다. 이 값이 만족한 아이의 최대 수입니다.
C++ 구현 예시
아래 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < g.size() && j < s.size()) {
if (g[i] <= s[j])
i++;
j++;
}
return i;
}
};
main(){
Solution ob;
vector<int> v = {1,2}, v1 = {1,2,3};
cout << (ob.findContentChildren(v, v1));
}입력
{1,2}, {1,2,3}출력
2
복잡도 분석
정렬에 걸리는 시간이 지배적이므로 시간 복잡도는 O(n log n + m log m)(n은 아이 수, m은 쿠키 수)이며, 정렬된 배열 위에서 투 포인터를 사용하기 때문에 공간 복잡도는 O(1)입니다. 작은 쿠키부터 순서대로 확인하되, 만족시킬 수 있는 아이부터 차례로 배정하는 것이 이 그리디 전략의 핵심입니다.