Leetcode 문제 455번 Assign Cookies

문제출처 : 

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

Assign Cookies - LeetCode

leetcode 455번 문제 - Assign Cookies

문제를 간단히 해석하자면,

당신이 자녀가 있는 부모이고 쿠키를 주고 싶다고 한다. (단, 각 어린이에게 최대 하나의 쿠키를 제공해야 합니다.) 
각각의 아이들은 아이가 만족할 쿠키의 최소 크기인 g[i]라는 greed factor를 가지고 있고, 각 쿠키 j의 크기는 s[j]입니다. s[j] >= g[i]인 경우, 쿠키 j를 child i에 할당할 수 있으며 child i는 만족할 것입니다. 너의 목표는 컨텐츠 하위 항목 수를 maximize하고 최댓값을 출력하는 것입니다.

예 1:

입력: g = [1,2,3], s = [1,1] 
출력: 1
설명: 3명의 자녀와 2개의 쿠키가 있습니다. 3자녀의 greed factor는 1, 2, 3이다. 그리고 쿠키가 2개 있더라도 크기가 모두 1이므로 greed factor가 1인 아이만 만들 수 있습니다. 1을 출력해야 합니다.

예 2:

입력: g = [1,2], s = [1,2,3]
출력: 2
설명: 2명의 자녀와 3명의 쿠키가 있습니다. 2자녀의 greed factor는 1, 2입니다. 쿠키가 3개 있고 그 크기는 모든 아이들을 만족시킬 만큼 큽니다. 2를 출력해야 합니다.

---

저는 해당 문제를 각각 주어진 vector를 sort하여 앞에서부터 서로 값을 비교하는 형식으로 구현하였습니다. 

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

---

다음과 같이 마출 수 있었습니다. 잘 실행되지 않았던 부분은 break하기 전의 j값을 가지고 왔어야했는데 그러지 못하여 Wrong Answer를 출력했었습니다.

https://github.com/gurcks8989/CodingTest/blob/master/LeetCode/P455_Assign_Cookies.cpp

GitHub - gurcks8989/CodingTest: BackJoon_study_with_c++

 

훈수, 조언 언제나 환영입니다.