[그리디] 리트코드 455: 쿠키 부여

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


시작: 21.05.12 11:42
끝: 21.05.12 11: 52
성공: correct

[아이디어]
그리드 팩터가 작은 애들 순서대로, 작은 쿠키 먼저 준다.
둘다 최소힙으로 관리.

[시간복잡도]
힙에서 빼는 연산을 쿠키 개수 or 애들 수 만큼 해야함
O(nlogn)


[실수]
if eles에서 else에 :를 안 썼다.

[검색]
heapq 사용법

1. 리스트를 힙으로 만들기
heapq.heapify(g)

2. pop하기
heapq.heappop(g)

[교재풀이1과 비교]
꼭 pop을 안 하고, 그냥 리스트를 읽기만 해도 해결 가능한 문제다.
자료를 삭제할 필요가 없으면 그냥 읽기만 하자.

"""
import heapq


class Solution:
    # 내 풀이
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        heapq.heapify(g)
        heapq.heapify(s)
        
        count: int = 0
        while (s and g):
            #greed factor
            gf = heapq.heappop(g)

            # cookie size
            cs = heapq.heappop(s)
            while (s and cs < gf):
                cs = heapq.heappop(s)
            
            if (cs >= gf):
                count += 1
            else:
                break
                
        return count
    
    
    # 교재 풀이1: 그리디
    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: 이진 검색
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        
        result = 0
        for i in s:
            # 이진 검색으로 더 큰 인덱스 탐색
            index = bisect.bisect_right(g, i)
            if index > result:
                result += 1
        
        return result