← 전체 회차
A-005● Day 052026.05.07mediumleetcode #347neetcode150

상위 K개 빈도 요소

#array#hash-table#divide-and-conquer#sorting#heap-priority-queue#bucket-sort#counting#quickselect
↗ leetcode #347 · top-k-frequent-elements
01

문제

· problem
P.005

상위 K개 빈도 요소

↗ leetcode #347

정수 배열 nums와 정수 k가 주어졌을 때, 가장 자주 나타나는 k개의 요소를 반환하세요. 답은 어떤 순서로든 반환할 수 있습니다. 팔로우업: 알고리즘의 시간 복잡도는 O(n log n)보다 나아야 합니다. 여기서 n은 배열의 크기입니다.

제약
  • · 1 ≤ nums.length ≤ 10^5
  • · -10^4 ≤ nums[i] ≤ 10^4
  • · k is in the range [1, the number of unique elements in the array]
  • · The answer is guaranteed to be unique
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[1,1,1,2,2,3]
2
[1,2]
example 2input → output
[1]
1
[1]
example 3input → output
[1,2,1,2,1,2,3,1,3,2]
2
[1,2]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    반환된 요소들의 순서가 중요한가요?
  • ☐
    배열에 음수가 포함될 수 있나요?
  • ☐
    k가 항상 고유 요소의 개수 이하인가요?
  • ☐
    가장 적게 나타나는 k개의 요소를 반환해야 하나요?
  • ☐
    값이 같은 요소들을 구분해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 빈도 카운터 초기화
○
count = {}
○
count = []
○
count = set()
step 2· 빈도 버킷 배열 초기화
○
freq = [[] for i in range(len(nums) + 1)]
○
freq = [[] for i in range(len(nums))]
○
freq = {}
step 3· 배열을 순회하며 빈도 계산│ 중첩
○
count[n] = 1 + count.get(n, 0)
○
count[n] = count.get(n, 1) + 1
○
count[n] += 1
step 4· 빈도별로 요소를 버킷에 추가│ 중첩
○
freq[c].append(n)
○
freq[n].append(c)
○
freq[c] = n
step 5· 높은 빈도부터 역순으로 순회 및 수집
○
for i in range(len(freq) - 1, 0, -1):
○
for i in range(len(freq)):
○
for i in range(len(freq) - 1, -1, -1):
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3
        count = {}
4
        freq = [[] for i in range(len(nums) + 1)]
5
6
        for n in nums:
7
            count[n] = 1 + count.get(n, 0)
8
        for n, c in count.items():
9
            freq[c].append(n)
10
11
        res = []
12
        for i in range(len(freq) - 1, 0, -1):
13
            res += freq[i]
14
            if len(res) == k:
15
                return res
16
                
17
18
        # O(n)
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[1,1,1,2,2,3]
2
→
[1,2]
case 2
[1]
1
→
[1]
case 3
[1,2,1,2,1,2,3,1,3,2]
2
→
[1,2]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.