6. Top K Frequent Elements

📊 [Python 문제풀이] Top K Frequent Elements — 정렬 vs heapq 완벽 비교

 

이번 글에서는 LeetCode의 인기 문제 중 하나인

“Top K Frequent Elements (가장 많이 등장한 K개의 숫자 구하기)” 문제를

두 가지 방식으로 풀이하고 비교한다:

 

1. dict + sorted()를 활용한 직관적 풀이
2. heapq를 활용한 고급 최적화 풀이

 

각 방식의 코드, 이론, 시간복잡도, 상황별 장단점까지 모두 정리한다.

 

---

 

🧠 문제 설명

 

**정수 배열 nums와 정수 k**가 주어졌을 때,

가장 자주 등장한 숫자 k개를 반환하라.

반환 순서는 상관없다.

 

---

 

📥 입력 예시

nums = [1,1,1,2,2,3]
k = 2

 

📤 출력 예시

[1, 2]

→ 1은 3번, 2는 2번 등장했기 때문에 상위 2개는 [1, 2]이다.

 

---

 

🧩 풀이 ① — 정렬 기반 (dict + sorted + lambda)

 

 

✅ 핵심 아이디어

 

1. 각 숫자의 등장 횟수를 dict에 저장
2. 등장 횟수를 기준으로 정렬 (sorted, lambda)
3. 상위 k개 숫자만 추출

 

---

 

✅ 전체 코드

from collections import defaultdict
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = defaultdict(int)
        for num in nums:
            count[num] += 1

        sorted_items = sorted(count.items(), key=lambda x: x[1], reverse=True)
        return [item[0] for item in sorted_items[:k]]

 

---

 

🔍 코드 설명

 

 

① 등장 횟수 저장

count = defaultdict(int)
for num in nums:
    count[num] += 1

 

• defaultdict(int)는 키가 없으면 자동으로 0으로 초기화된다.

 

---

 

② 등장 횟수 기준 정렬

sorted_items = sorted(count.items(), key=lambda x: x[1], reverse=True)

 

• count.items()는 (숫자, 등장횟수) 형태의 튜플 리스트
• lambda x: x[1]는 등장 횟수를 기준으로 정렬
• reverse=True는 내림차순 정렬

 

---

 

③ 숫자만 추출

[item[0] for item in sorted_items[:k]]

 

• 상위 k개의 숫자만 리스트로 추출

 

---

 

✅ 시간 복잡도

 

• 등장 횟수 계산: O(n)
• 정렬: O(n log n)
• 슬라이싱 및 추출: O(k)

 

➡️ 총합: O(n log n)

 

---

 

⚡ 풀이 ② — heapq 기반 고급 풀이 (빠름)

 

 

✅ 핵심 아이디어

 

• heapq의 nlargest()를 사용하여 정렬 없이 상위 k개만 추출
• 성능이 더 뛰어나고 메모리 효율적

 

---

 

✅ 전체 코드

from collections import Counter
import heapq
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        return [num for num, _ in heapq.nlargest(k, count.items(), key=lambda x: x[1])]

 

---

 

🔍 코드 설명

 

 

① 등장 횟수 세기

count = Counter(nums)

 

• Counter는 리스트 요소의 등장 횟수를 자동으로 세어준다.

 

---

 

② heapq로 상위 k개 추출

heapq.nlargest(k, count.items(), key=lambda x: x[1])

 

• 등장 횟수 기준으로 k개만 힙에서 유지 → 빠름
• 시간 복잡도: O(n log k)

 

---

 

③ 숫자만 추출

[num for num, _ in ...]

 

• 튜플에서 숫자만 추출해 리스트로 반환

 

---

 

✅ 시간 복잡도

 

• 등장 횟수 계산: O(n)
• heapq 추출: O(n log k)
• 추출: O(k)

 

➡️ 총합: O(n log k) → 대용량 데이터에 훨씬 유리

 

---

 

📊 정렬 풀이 vs heapq 풀이 비교

항목정렬 기반 풀이heapq 기반 풀이

코드 직관성	✅ 좋음	⚠️ 약간 복잡
시간복잡도	O(n log n)	✅ O(n log k)
메모리 사용	전체 정렬 필요	✅ k개만 유지
대용량 처리	⚠️ 비효율적	✅ 매우 효율적
실무 활용	충분히 가능	✅ 실시간 분석 등에 적합

 

---

 

✅ 마무리 정리

 

이 문제는 Top-K 빈도 추출이라는 패턴으로,

Python에서는 dict, sorted, lambda, heapq 등 다양한 기법을 배울 수 있는 아주 좋은 예제이다.

 

• 초반에는 정렬 기반 풀이로 구조를 익히고,
• 익숙해지면 heapq 기반으로 최적화하는 연습이 좋다.