[LeetCode] 455. Assign Cookies

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

Assign Cookies - LeetCode

leetcode - Assign Cookies

문제 유형 : 그리디, 정렬

문제 난이도 : Easy

 

문제

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

 

당신이 좋은 부모이고 아이들에게 쿠키를 주려고 한다고 하자.

그러나, 당신은 최대 1개씩만 줄 수 있다.

각 i번째 아이는 g[i]의 탐욕 수치가 있다. 이는 그 아이들이 받아야 하는 쿠키의 최소 사이즈이다.

각 j번째 쿠키는 s[j]의 크기 수치가 있다.

우리는 s[j] >= g[i]일때 쿠키 j를 i번째아이에게 줄 수 있다.

당신은 최대한 많은 아이에게 쿠키를 주려고 한다.

쿠키를 받는 가장 많은 아이의 수를 구하시오.

 

 

풀이

우선, 두 가지 배열을 오름차순으로 정렬해준다.

 

두 가지 인덱스를 가리키는 i와 j를 만든다.

개수를 세는 변수 cnt도 하나 만들어준다.

 

while문을 이용하여 i와 j가 각각의 배열의 범위 안에 들어오는 조건에서 개수를 세주면 된다.

만약 s[j] < g[i]라면, j의 크기만 1 올린다.

쿠키를 줄 수 있다면, i와 j, cnt를 각각 1씩 올린다.

반복문이 끝나면 cnt를 반환시키면 된다.

 

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int i = 0;
        int j = 0;
        int cnt = 0;
        while(i < g.size() && j < s.size()) {
            if(g[i] > s[j]) {
                j++;
                continue;
            }
            cnt++;
            i++;
            j++;
        }

        return cnt;
    }
};