[Leetcode]455. Assign Cookies

김지원·2022년 4월 7일

Binary Search array greedy leetcode python

Python으로 공부하는 코딩테스트

목록 보기

31/82

📄 Description

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마다 그리드 팩터(greedy factor) $g_i$ 를 갖고 있으며, 이는 아이가 만족하는 최소 쿠키의 크기를 말한다. 각 쿠키 j는 크기 $s_j$ 를 갖고 있으며, $s_j>=g_i$ 이어야 아이가 만족하며 쿠키를 받는다. 최대 몇 명의 아이들에게 쿠키를 줄 수 있는지 출력하라.

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

🔨 My Solution

s 중 어떤 쿠키를 먼저 줘야 하는가?
g 중 어떤 child에게 먼저 쿠키를 줘야 하는가?

👉 사이즈가 가장 작은 쿠키를 content 정도가 가장 작은 child에게 먼저 줘야 한다.

💻 My Submission

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        child=cookie=0
        
        g.sort()
        s.sort()
        
        num=0
        
        while child<len(g) and cookie<len(s):
            if g[child]<=s[cookie]: 
                num+=1
                child+=1
            cookie+=1
        return num

💭 Another approach (1)

👉 Opposite direction

사이즈가 가장 큰 쿠키를 content 정도가 가장 큰 child에게 준다.

class Solution:
    def findContentChildren(self, g, s):
        g.sort(reverse=True)
        s.sort(reverse=True)
        i = j = 0
        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                j += 1
            i += 1
        return j

💭 Another approach (2)

👉 Binary Search, 이진 검색

2개의 리스트를 모두 번갈아가며 탐색하는 게 아니라 하나의 리스트를 순회하면서 다른 하나는 이진 검색으로 찾는다.

class Solution:
    def findContentChildren(self, g, s):
    	g.sort()
        s.sort()
        
        result=0
        for i in s:
        	# 이진 검색으로 더 큰 인덱스  탐색
            index = bisect.bisect_right(g, i)
            if index > result:
            	result+=1
		return result

이진 검색 시 사용하는 bisect_left()는 찾아낸 값의 해당 위치 인덱스를 리턴하고, bisect_right()는 사용하여 찾아낸 값의 다음 인덱스를 리턴한다.

References

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

https://leetcode.com/problems/assign-cookies/discuss/94063/Simple-PYTHON-O(nlogn)

파이썬 알고리즘 인터뷰(95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트), 박상길 지음