🖥️ 문제
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.
📝 풀이
import java.util.Arrays;
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int i = g.length - 1;
int j = s.length - 1;
while (i >= 0 && j >= 0) {
if (s[j] >= g[i]) {
count++;
j--;
}
i--;
}
return count;
}
}
문제는 아이들에게 최대한 많은 쿠키를 나눠주어 만족시켜야하는 것이다.
먼저 아이의 욕심 지수 배열 g와 쿠키의 크기 배열 s를 오름차순으로 정렬한다. 이는 작은 쿠키를 먼저 주고, 작은 욕심을 가진 아이부터 만족시키기 위함이다.
count 만족한 아이의 수
i 아이 배열 g의 끝에서부터 시작하는 인덱스
j 쿠키 배열 s의 끝에서부터 시작하는 인덱스
이후 i와 j를 각각 감소시키면서 아이와 쿠키를 비교한다. 만일, 현재 쿠키 s[j]가 아이의 g[i]의 욕심 지수보다 크거나 같다면, 아이는 만족하게 되고 count를 증가시킨 후, 자녀와 쿠키의 인덱스를 모두 감소시킨다.
또한 만약 현재 쿠키가 아이를 만족시키기에 충분하지 않다면, 그 아이를 건너뛰고(즉, i만 감소시켜서) 다음 아이로 넘어간다.
