[파이썬 알고리즘 인터뷰][해시테이블] 상위 K 빈도 요소

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

---

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

 

문제 정의

상위 k번 이상 등장하는 요소 출력

 

책에서 구현된 코드

# heapq 이용
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
    freqs = collections.Counter(nums)
    freqs_heap = []
    for f in freqs:
        heapq.heappush(freqs_heap, (-freqs[f], f))
    
    topk = list()
    for _ in range(k):
        topk.append(heapq.heappop(freqs_heap)[1])
    
    return topk
    
# Counter
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
    return list(zip(*collections.Counter(nums).most_common(k)))[0]

 

기억해야할 기법

• zip()
  
  • 2개 이상의 시퀀스를 짧은 길이 기준으로 일대일 대응 튜플 시퀀스로 바꿔줌
  • a = [1, 2, 3, 4]
    b = [5, 6, 7]
    list(zip(a, b)) -> [(1, 5), (2, 6), (3, 7)]
• 아스테리스크(*)
  • 시퀀스 언패킹 연산자
    - 시퀀스를 풀어헤치는 연산자
    - 언패킹
    fruits = ['lemon', 'pear', 'banana']
    print(*fruits) -> lemon pear banana
    - 패킹
    def f(*params):
        print(params)
    >>> f('a', 'b', 'c')
    ('a', 'b', 'c')
  • (**)
    - 키/값 페어를 언패킹하는데 사용
    dic = {'a':1, 'b':2}
    nw_idc = {*dic, 'c':3} -> {'a':1, 'b':2, 'c':3}

 

내가 구현한 코드

def topKFrequent(nums: list[int], k: int) -> list[int]:
    return [k for k,v in Counter(nums).most_common(k)]

• 속도는 비슷하다
• 책에서 구현한 내용은 list()[0] 이 부분이 개인적으로 부자연스러워보인다