[leetcode] 455. Assign Cookies

455. Assign Cookies

문제

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

i번째 아이는 g[i] 이상 사이즈의 쿠키를 받아야 만족하고, j번째 쿠키의 사이즈를 s[j]라고 한다.

이때, s[j] >= g[i]일 때 i번째 아이에게 j번째 쿠키를 줄 수 있다. 이 문제의 목적은 최대한 많은 아이들에게 만족할만한 쿠키를 나눠주는 것이다.

풀이

최대한 많은 아이들에게 쿠키를 나눠주어야 하므로, 각 아이들이 만족할만한 쿠키 사이즈 중 가장 작은 사이즈를 나눠줘야 한다.

따라서, 아이들이 만족할 쿠키 크기 벡터인 g 벡터를 오름차순으로 정렬하고 줄 수 있는 쿠키 사이즈 개수 벡터인 s 벡터를 오름차순으로 정렬해야 한다. 정렬된 벡터들의 값을 비교하면, 각 아이에게 줄 수 있는 최소 크기의 쿠키를 줄 수 있다.

답안

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        
        int idxS = 0;
        int countG = 0;
        
        for(int i = 0; i < g.size(); i++) {
            for(int j = idxS; j < s.size(); j++) {
                if(g[i] <= s[j]){
                    idxS = j + 1;
                    countG++;
                    break;
                }
            }
        }
        return countG;
    }
};