[Leetcode] 455. Assign Cookies

Identifying the Problem

보유한 쿠키로 만족시킬 수 있는 최대한의 아이들의 수를 구한다.

g[ ] : 아이들 별로 만족하는 쿠키 사이즈

s[ ] : 보유한 사이즈별 쿠키

Organizing thoughts

1)  s[j] >= g[i] 꼴을 만족하면 아이에게 쿠키를 줄 수 있다.

2)  아이가 만족하는 쿠키와 주어진 쿠키 사이즈가 최대한 똑같아야 한다.

3) s의 길이가 길든, g의 길이가 길든 탐색은 s 길이만큼 진행해야 한다.

4)  단, s가 더 길 때, 모든 아이들에게 쿠키를 나누어 준 경우, 탐색을 중단한다. 

Sourcecode

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) 
    {
        int k = 0;
        
        sort(g.begin(), g.end()); // g,s를 오름차순 정렬
        sort(s.begin(), s.end());
        
        for(int i = 0; i<s.size(); i++)
        {
            if(g[k] <= s[i])
                k++;
            if(k == g.size()) break;

        }
        return k;
    }
};