455. Assign Cookies

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

아이들이 받을 수 있는 쿠키, 쿠키의 사이즈..? 배열이 주어졌을때 쿠키를 받을 수 있는 아이들의 최대 수를 구하여라

문제에서 주어진 테스트케이스에서는 정렬되어 주어졌지만 문제에서 정렬된(sorted) 값이라는 조건이 없기 때문에 먼저 정렬해주어야한다.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        res = 0

        for i in s:
            idx = bisect_right(g,i)
            if idx > res:
                res +=1
        return res

bisert_right를 활용하면 g,s 두 개를 모두 탐색하지 않고 하나의 리스트를 순화하며 다른 하나는 이진 탐색을 통하여 찾을 수 있다.

만약 idx가 현재 부여한 아이들보다 크다면, 줄 수 있는 아이들의 수res를 1명 더 count한다.

*bisect_right(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 반환