(C++) - LeetCode (easy) 455. Assign Cookies

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

Assign Cookies - LeetCode

greedy 또는 이분탐색으로 푼 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

g와 s를 오름차순으로 정렬해줍니다.

📔 풀이과정

cookie 크기가 아이의 greed 크기 이상이라면 배분해줄 수 있습니다. 따라서 두 가지 방향으로 구현을 고려해 볼 수 있습니다.

📑 이분탐색

1. greed 이상인 lower_bound를 s에서 찾아줍니다.

2. 찾았다면 배분 가능하므로 ans를 1씩 더해줍니다.

 

📑 greedy

오름차순으로 정렬되어 있으므로 s[j] >= g[i]를 배분해줄 수 있다면 바로 배분해줍니다.

📔 정답 출력 | 반환

ans를 반환해줍니다.

---

📕 Code

📔 C++

 📑 이분탐색

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

        int ans = 0;
        for(auto greed : g) {
            auto it = lower_bound(s.begin(), s.end(), greed);
            if(it == s.end()) continue;
            s.erase(it);
            ans++;
        }
        return ans;
    }
};

 

 📑 greedy

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

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

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.