[파이썬 알고리즘 인터뷰][그리디] 쿠키 부여

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

g 이상인 값을 s와 매칭할 수 있는 최대 개수

 

책에서 구현된 코드

# 그리디 알고리즘
from typing import List

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

# 이진 탐색
import bisect
from typing import List


class Solution:
    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

 

기억해야할 기법

• 이런 유형 문제를 많이 접해서 접근 방식을 고쳐야할 것 같다
  
  • sort를 해서 그리디 알고리즘이 아닌데, 그리디한 방식으로 문제를 접근하지 않는 것 같다
  • 그리디 알고리즘에 대한 나의 숙련도가 문제인줄 알았는데, 이진탐색을 응용할 생각도 못했다

 

내가 구현한 코드

from typing import List
from collections import Counter
from bisect import bisect_left

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        answer = 0
        cnt_g, cnt_s = Counter(g), Counter(s)
        key_g = sorted(cnt_g, reverse=True)
        key_s = sorted(cnt_s)

        for i in key_g:
            num_g = cnt_g[i]
            j = bisect_left(key_s, i)
            while j < len(key_s):
                num_s = cnt_s[key_s[j]]
                if num_s >= num_g:
                    cnt_s[key_s[j]] -= num_g
                    answer += num_g
                    break
                else:
                    answer, num_g = answer + num_s, num_g - num_s
                    del key_s[j]

        return answer

• 조잡한 방식으로 인해 책에서 구현한 알고리즘보다 2배 정도 느리다