LeetCode 455 - Assign Cookies (Easy)

출처: https://leetcode.com/problems/assign-cookies/

// LeetCode 455 - Assign Cookies (Easy)
// https://leetcode.com/problems/assign-cookies/

// 문제 설명
// 아이마다 greed factor g[i] (만족하는 최소 쿠키 크기)가 있고,
// 쿠키마다 크기 s[j]가 있다. s[j] >= g[i] 이면 쿠키 j를 아이 i에게 줄 수 있다.
// 아이 한 명당 쿠키는 최대 1개. 만족하는 아이 수를 최대로 만들어 반환하라.

// 제약 조건
// 1 <= g.length <= 3 * 10^4
// 0 <= s.length <= 3 * 10^4   (쿠키가 0개일 수 있음)
// 1 <= g[i], s[j] <= 2^31 - 1

// Example 1
// Input : g = [1,2,3], s = [1,1]
// Output: 1
//   쿠키 크기가 둘 다 1이라 greed=1인 아이 하나만 만족.
//
// Example 2
// Input : g = [1,2], s = [1,2,3]
// Output: 2
//   쿠키가 충분히 커서 두 아이 모두 만족.

// 접근 — 그리디 + 투 포인터
// 가장 욕심 작은 아이에게 그 아이를 만족시키는 "가장 작은" 쿠키를 배정하면
// 큰 쿠키를 아껴 더 많은 아이를 만족시킬 수 있다.
// 1) g, s 둘 다 오름차순 정렬
// 2) 두 포인터 i(아이)·j(쿠키)를 함께 전진:
//    - s[j] >= g[i] 이면 배정 성공 → 아이·쿠키 둘 다 다음으로, count++
//    - 부족하면 더 큰 쿠키를 찾아 쿠키 포인터만 전진
// 시간 O(n log n + m log m), 공간 O(1)

#include <algorithm>
#include <vector>
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 count = 0;
        int i = 0;  // 아이 인덱스 (욕심 작은 순)
        int j = 0;  // 쿠키 인덱스 (작은 순)

        while (i < (int)g.size() && j < (int)s.size())
        {
            if (s[j] >= g[i])  // 이 쿠키로 현재 아이 만족
            {
                ++count;
                ++i;
            }
            ++j;  // 만족했든 못 했든 이 쿠키는 소비(또는 너무 작아 버림)
        }
        return count;
    }
};