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()
는 찾아낸 값의 다음 인덱스를 리턴한다는 차이
-
Author And Source
이 문제에 관하여(82. Assign Cookies), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@corone_hi/82.-Assign-Cookies저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)