11장. 해시 테이블(6) - 예제(상위 K빈도 요소)

 

 

상위 k번 이상 등장하는 요소를 추출하라
입력: num = [1,1,1,2,2,3] , k=2
출력: [1,2]

 

 

풀이1. Counter와 우선순위 큐(힙)를 활용한 방법

[해결 아이디어]

• collections.Counter를 사용해 각 요소의 빈도 수를 구하고, 상위 k개를 heapq 모듈의 힙을 이용해 추출한다.
• 파이썬에서 힙은 최소 힙만 지원하므로, 빈도를 음수로 변환하여 가장 큰 빈도부터 추출할 수 있도록 만든다.

[단계별 풀이]

 

1. 빈도 계산: Counter로 요소별 빈도를 계산

import collections

num = [1,1,1,2,2,3]
freqs = collections.Counter(num) # 결과: # Counter({1: 3, 2: 2, 3: 1})

 

 

 

2. 힙에 삽입: 각 요소의 빈도 수를 음수로 변환하여 힙에 삽입한다. heappush()를 사용하면 삽입마다 힙이 자동 정렬된다. 

import heapq

freqs_heap = []
for f in freqs:
    heapq.heappush(freqs_heap, (-freqs[f], f))

 

3. 결과 추출: heappop()을 통해 상위 k개를 추출한다. 

topk = list()

for _ in range(k):
    topk.append(heapq.heappop(freqs_heap)[1])

 

 

 

[전체 코드]

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()
    # k번 만큼 추출, 최소힙이므로 가장 작은 음수 순으로 추출
    for _ in range(k):
        topk.append(heapq.heappop(freqs_heap)[1])
        
    return topk

 

 

---

 

풀이2. 파이썬의 most_common() 메서드 활용

[해결 아이디어]

• Counter의 most_common() 메서드를 사용하면 빈도 수가 높은 순서대로 요소를 쉽게 추출할 수 있다. 
• 이 요소를 사용해 상위 k개의 요소를 한 줄 코드로 구할 수 있다. 

[단계별 풀이]

1. most_common() 사용: most_common(k)을 통해 상위 k개의 요소를 빈도와 함께 튜플 형식으로 반환한다. 

collections.Counter(num).most_common(2)
# 결과: [(1, 3), (2, 2)]

 

2. 출력 형식 맞추기: zip()과 *를 사용해 요소만 추출하여 리스트 형태로 반환한다. (여기서는 튜플로 반환)

list(zip(*collections.Counter(num).most_common(2)))[0]
# 결과: (1, 2)

 

[전체 코드]

def topKFrequent(self, nums: List[int], k:int) -> List(int):
    return list(zip(*collections.Counter(nums).most_common(k)))[0]

 

 

 

이번 글에서는 zip 함수와 *의 활용 방법에 대해 설명하지 않았지만, 다음 글에서 자세히 다룰 예정입니다.