Leetcode [Greedy] 455. Assign Cookies [Easy]

in CodingTest

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.

Example 1:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.   
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.   
You need to output 1.

Example 2:

Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children, 
You need to output 2.

Constraints:

1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

문제의 요지는 아래와 같습니다.

아이들의 수와, 각 아이들이 원하는 쿠키의 갯수가 g로 주어집니다.
한번에 제공되는 쿠키의 양과, 총 쿠키의 겟수가 s로 주어집니다.

아이들이 원하는 쿠키의 갯수를 충족할 수 있다면 s[j] >= g[i] 결과값을 +1 해줍니다.
만약 아이들이 원하는 쿠키의 갯수가 충족하지 못한다면 다음으로 넘어갑니다.
해당 비교는 아이들을 다 확인했거나, 쿠키 개수를 다 확인했을때 멈춥니다.

코드로 나타내면 아래와 같습니다.
아이들이 원하는 가장 작은 쿠키양만큼 나누어주어야 가장 많은 쿠키를 나누어 줄 수 있기 떄문에
오름차순으로 정렬하여 아이들이 원하는 쿠키를 만족하여 줄 수 있는지 확인해 나갑니다.
만약 만족한다면 결과값을 +1 해주고 아이들의 인덱스를 +1 해줍니다.
비교한 쿠키의 인덱스는 확인 결과여부에 상관없이 인덱스를 +1 해줍니다.

두번째 예제를 예로들어 보자면 아래와 같습니다.

sortedChildren = [1,2]
sortedCookies = [1,2,3]

1번째 아이가 원하는 쿠키의 개수는 1개, 그리고 줄 수 있는 쿠키도 1개,   
그러므로 결과를 +1 해주고, 다음 아이를 확인합니다. (chidrenIndex +1)
쿠키의 인덱스도 +1 해줍니다.

2번쨰 아이가 원하는 쿠키의 개수는 2개, 그리고 지금 줄 수 있는 쿠키의 개수는 2개
그러므로 위와같은 로직을 수행합니다.

3번째 진행하기 전에, 이미 모든 아이에게 쿠키를 나누어 주었으므로 반복문이 종료되며
총 +2회 되어있는 결과값 2를 리턴해줍니다.

코드로 나타내면 아래와 같습니다.

class Solution {
    func findContentChildren(_ g: [Int], _ s: [Int]) -> Int {
        var children = g.sorted()
        var cookies = s.sorted()

        var chIndex = 0
        var cooIndex = 0

        var result = 0

        while chIndex < children.count && cooIndex < cookies.count {
            if children[chIndex] <= cookies[cooIndex] {
                result += 1
                chIndex += 1
            }
            cooIndex += 1
        }

        return result
    }
}