문제
LeetCode 347. Top K Frequent Elements. 정수 배열 nums 와 정수 k 가 주어지면 가장 자주 나온 원소 k 개를 반환한다. 순서는 상관없다.
nums = [1,1,1,2,2,3], k = 2 → [1,2]
k 는 1 이상이고 고유 원소 수 이하이며, 답은 하나로 정해진다고 보장된다. 문제 끝에 ” 보다 빠르게 풀어 보라” 는 follow-up 이 붙어 있다.
아래에서 n 은 배열 길이, m 은 고유 원소 수다. 항상 k ≤ m ≤ n 이다.
풀이 1: 세고 정렬하기
가장 먼저 떠오르는 방법이다. 원소별 빈도를 해시맵에 세고, 빈도 내림차순으로 정렬한 뒤 앞에서 k 개를 자른다.
from collections import Counter
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
count = Counter(nums)
return sorted(count, key=count.get, reverse=True)[:k]시간 복잡도가 O(n + m log m) 인 이유
단계별로 나누면 다음과 같다.
| 단계 | 하는 일 | 시간 |
|---|---|---|
Counter(nums) | 원소 n 개를 한 번씩 훑으며 해시맵에 +1 | |
sorted(...) | 고유 원소 m 개를 빈도 기준으로 정렬 | |
[:k] | 앞에서 k 개 복사 |
첫 항 은 빈도를 세는 단계에서 나온다. 슬라이스의 는 k ≤ m 이라 정렬 항 에 묻힌다.
모든 원소가 서로 다르면 m = n 이므로 최악은 이다. 그래서 그냥 이라고 말해도 틀리지 않는다. 다만 두 항으로 나눠 두면 중복이 많은 입력에서 실제로 더 빠르다는 점이 드러난다. time complexity 표기는 해당 노트 참고.
풀이 2: 크기 k 짜리 min-heap
풀이 1은 m 개를 전부 정렬하지만 필요한 것은 상위 k 개뿐이다. Heap 을 쓰면 전체 정렬 없이 상위 k 개만 유지할 수 있다.
import heapq
from collections import Counter
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
count = Counter(nums)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap) # 빈도가 가장 낮은 것을 버린다
return [num for freq, num in heap]heapq.nlargest(k, count, key=count.get) 한 줄로도 같은 결과가 나온다. 내부에서 하는 일이 위 코드와 같다.
큰 값 k 개를 구하는데 왜 min-heap 인가
힙에서 필요한 연산이 “큰 값을 꺼내기” 가 아니라 “지금 들고 있는 k 개 중 가장 작은 값을 찾아서 버리기” 이기 때문이다.
힙을 “상위 k 명 명단” 으로 보면 heap[0](최솟값)은 그 명단의 커트라인이다. 새 값이 들어올 때마다 명단의 꼴찌 하나를 내보낼지만 결정하면 된다. 꼴찌를 에 찾고 에 내보내는 자료구조가 min-heap 이다.
k = 2 이고 빈도가 5, 1, 3, 8 순서로 들어오는 경우를 따라가 보면 다음과 같다.
| 들어온 빈도 | push 직후 힙 | 크기가 k 를 넘으면 pop | 남은 힙 |
|---|---|---|---|
| 5 | [5] | - | [5] |
| 1 | [1, 5] | - | [1, 5] |
| 3 | [1, 5, 3] | 1 을 버린다 | [3, 5] |
| 8 | [3, 5, 8] | 3 을 버린다 | [5, 8] |
끝나고 남은 [5, 8] 이 상위 2 개다.
max-heap 으로도 풀 수는 있다. 전부 넣은 뒤 큰 것부터 k 번 꺼내면 된다. 이 경우 힙에 m 개가 모두 들어가므로 시간은 , 힙 메모리는 이다. min-heap 방식은 힙 크기가 k 를 넘지 않아서 입력이 끝없이 들어오는 스트림에서도 쓸 수 있다.
정리하면 방향이 반대다.
- 큰 값
k개 → 크기k의 min-heap - 작은 값
k개 → 크기k의 max-heap
시간 복잡도가 O(n + m log k) 인 이유
| 단계 | 하는 일 | 시간 |
|---|---|---|
Counter(nums) | 빈도 세기 | |
| 반복문 | 고유 원소 m 개를 하나씩 push, 필요하면 pop | m 번 × |
push 와 pop 은 트리 높이만큼 걸린다. 힙 크기를 k 로 유지하므로 높이가 다. 풀이 1과 비교하면 이 로 바뀐 것이다. m 이 100만이고 k 가 10이면 , 이다. k 가 m 에 가까우면 차이가 없다.
공간은 힙만 보면 지만, 빈도를 세는 Counter 가 고유 원소마다 칸을 하나씩 써서 이다. 그래서 전체로는 이다.
heapq 는 리스트를 힙으로 다룬다
Python 의 heapq 에는 힙 클래스가 따로 없다. 평범한 리스트가 곧 힙이고, heapq 의 함수들은 그 리스트가 힙 규칙을 지키도록 원소를 옮겨 준다.
리스트 하나로 트리를 표현하는 방법
힙은 완전 Binary Tree 다. 완전 이진 트리는 위에서부터 빈칸 없이 채워지므로 배열 하나에 그대로 담을 수 있다. 인덱스 i 의 자식은 2i + 1 과 2i + 2 이고, 부모는 (i - 1) // 2 다.
리스트: [1, 3, 2, 7, 5]
1 인덱스 0
/ \
3 2 인덱스 1, 2
/ \
7 5 인덱스 3, 4
힙 규칙은 “부모 ≤ 자식” 하나뿐이다. 리스트가 정렬돼 있는 것은 아니고, 보장되는 것은 heap[0] 이 최솟값이라는 것뿐이다. 앞의 표에서 push 직후 힙이 [1, 5, 3] 처럼 정렬되지 않은 모양으로 나온 것도 이 때문이다.
자주 쓰는 함수
표의 는 함수에 넘긴 리스트나 반복 가능한 객체에 든 원소 수다. 앞에서 배열 길이로 쓴 과 구분하려고 다른 문자를 썼다.
| 함수 | 하는 일 | 시간 |
|---|---|---|
heappush(h, x) | 맨 뒤에 붙인 뒤 부모보다 작으면 위로 올린다 | |
heappop(h) | h[0] 을 꺼내고 맨 뒤 원소를 루트에 올린 뒤 아래로 내린다 | |
h[0] | 최솟값 조회 | |
heapify(h) | 아무 리스트나 힙으로 정리한다 | |
nlargest(k, it, key=...) | 크기 k 힙으로 상위 k 개를 뽑는다 |
쓸 때 주의할 점
- min-heap 만 지원한다. max-heap 이 필요하면 값에
-를 붙여 넣고 꺼낼 때 다시-를 붙인다. - 튜플을 넣으면 첫 원소부터 비교한다. 그래서
(우선순위, 값)꼴로 넣는다. 위 풀이의(freq, num)이 이 형태다. - 리스트 그대로라서 규칙을 깨는 것도 막아 주지 않는다. 힙으로 쓰는 리스트에
append를 직접 하면h[0]이 최솟값이라는 보장이 사라진다. 넣고 빼는 것은heappush와heappop으로만 한다. h[-1]이 최댓값이라는 보장은 없다. 인덱스로 볼 수 있는 것은h[0]뿐이다.
풀이 3: 버킷 정렬
follow-up 의 가장 빠른 답이다. 빈도는 1 이상 n 이하의 정수다. 그래서 인덱스가 빈도인 배열을 만들어 원소를 넣고, 뒤에서부터 k 개를 모으면 비교 정렬 없이 끝난다.
from collections import Counter
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
result = []
for freq in range(len(buckets) - 1, 0, -1):
result.extend(buckets[freq])
if len(result) >= k:
return result[:k]nums = [1,1,1,2,2,3] 이면 buckets[3] = [1], buckets[2] = [2], buckets[1] = [3] 이 되고, 뒤에서부터 훑어 [1, 2] 를 얻는다.
빈도 세기 , 버킷 채우기 , 버킷 훑기 이라서 전체 이다. 버킷 배열 때문에 공간도 이다.
세 풀이 비교
| 풀이 | 방식 | 시간 | 공간 |
|---|---|---|---|
| 정렬 | 고유 원소 전체를 빈도순으로 정렬 | ||
| min-heap | 상위 k 개만 힙에 유지 | ||
| 버킷 정렬 | 빈도를 인덱스로 쓰는 배열 |
Counter.most_common(k) 한 줄로도 같은 결과가 나온다. CPython 의 구현은 k 가 주어지면 heapq.nlargest 를 부르므로, 하는 일은 min-heap 풀이와 같다. k 를 주지 않으면 전체를 정렬한다.
힙 풀이는 입력이 스트림이거나 k 가 작을 때 유리하고, 버킷 풀이는 빈도처럼 값의 범위가 n 이하로 묶여 있을 때만 쓸 수 있다. 정렬 전반은 sorting 참고.
같은 “크기 k 힙” 틀을 쓰는 문제로 LeetCode 973. K Closest Points to Origin 이 있다. 가까운 점, 즉 작은 값 k 개를 구하므로 거리에 - 를 붙인 max-heap 을 쓴다.