leetcode 455. Assign Cookies

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

최대한 많은 아이들에게 쿠키 나눠주기.

주의할 점 -> 그리디하게 배분하면 쉽게 풀 수 있는 문제지만, 예제에서는 모든 입력값이 정렬되어 있어 자칫 혼동될 수 있으나 원래 문제에는 정렬된 값이라는 제약이 없다는 점을 주의해야 한다. 따라서 코드 상단부에 먼저 정렬해주는 작업을 직접 진행해야한다.

풀이1. 그리디 알고리즘.

def findContentChildren(self, g: List[int], s: List[int]) -> int:
	g.sort()
    s.sort()
    
    child_i = 0 
    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

정렬 이후 크기를 비교해가며 아이가 만족하는 크기 if s[cookie_j] >= g[child_i]일 경우 다음 아이 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

2개의 리스트를 모두 번갈아 가면서 탐색하는 게 아니라 하나의 리스트를 순회하면서 다른 하나는 이진 검색으로 찾는 방법이다. 그런 다음 찾아낸 인덱스가 현재 부여한 아이들보다 클 경우에는 쿠키를 더 줄 수 있다는 말이 되므로, 줄 수 있는 아이들의 수를 1명 더 늘리는 방법.

bisect library?
: 원소들이 정렬된 리스트에서 특정 원소를 찾을 때 효과적인 라이브러리.

• bisect_left(list, data): 리스트에 데이터를 삽입할 가장 왼쪽 인덱스를 찾는 함수(리스트 내 정렬 순서를 유지).
• bisect_right(list, data): 리스트에 데이터를 삽입할 가장 오른쪽 인덱스를 찾는 함수(리스트 내 정렬 순서를 유지).

from bisect import bisect_left, bisect_right

g = [1,2,3,4,5]
i = 3

print(bisect.bisect_left(g, i))     # 2
print(bisect.bisect_right(g, i))    # 3

풀이3. 이진트리(힙 큐)

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) # pop하기
            
            # cookie size
            cs = heapq.heappop(s)
            while (s and cs < gf):
            	cs = heapq.heappop(s)
                
            if (cs >= gf):
            	count += 1
            else:
            	break
                
        return count

그리드 팩터가 작은 대들 순서대로, 작은 쿠키를 먼저 주며 둘다 최소힙으로 관리한다.

힙 자료구조 및 heapq module

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

• 최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
• 최대 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
  (키 값의 대소 관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않는다.)

1. heapq module -> heapq(priority queue) 알고리즘 제공
   모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.

Reference.

• Tony Park님의 블로그
• ember님의 블로그
• LittleFox 님의 힙 자료구조 정리