82. Assign Cookies

리트코드

• 아이들에게 1개씩 쿠키를 나눠줘야 한다. 각 아이 child_i마다 그리드 팩터(GreedFactor) gi를 갖고 있으며, 이는 아이가 만족하는 최소 쿠키의 크기를 말한다.
  각 쿠키 cookie_j는 크기 sj를 갖고 있으며, sj >= gi이어야 아이가 만족하며 쿠키를 받는다. 최대 몇명의 아이들에게 쿠키를 줄 수 있는지 출력하라.

1. 그리디 알고리즘 (180ms)

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        
        child_i = cookie_j = 0
        
        #만족하지 못할 때까지 그리디 진행
        while child_i < len(g) and cookie_j < len(s):
            if s[cookie_j] >= g[child_i]:
                child_i += 1
            cookie_j += 1
        
        return child_i
        

<쿠키의 크기와 아이가 만족하는 최소 쿠키의 크기>

• 그림에서 2번째 아이는 크기 2 이상의 쿠키를 원하지만, 2번째 쿠키도 크기가 1이기 때문에 줄 수 없다. 따라서 여기서 출력은 1이 된다.

• 이 문제는 그리디하게 배분하면 쉽게 풀 수 있는 문제다.

  단, 예제에서는 모든 입력값이 정렬되어 있어 자칫 혼동될 수 있으나 원래 문제에는 정렬된 값이라는 제약이 없다.

  따라서 코드 상단부에 먼저 정렬해주는 작업을 진행해야 한다.

• 정렬 이후에는 크기를 비교해가며 아이가 만족하는 크기 s[cookie_j] >= g[child_i]일 경우 다음 아이 child_i += 1로 차례를 넘어가는 형태로 구현할 수 있다.

2. 이진 검색 (184ms)

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

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

• 찾아낸 인덱스가 현재 부여한 아이들보다 클 경우에는 이 경우 더 줄 수 있다는 말이 되므로, 줄 수 있는 아이들의 수를 1명 더 늘린다.

• 이진 검색 시 사용하던 bisect_left()가 아니라 bisect_right() 를 사용했다.

  • bisect_left()는 찾아낸 값의 해당 위치 인덱스를 리턴

  • bisect_right()는 찾아낸 값의 다음 인덱스를 리턴한다는 차이