라이브 코딩에서 "정렬하면 되지 않나요?"라고 먼저 답하는 순간, 면접관의 다음 질문은 거의 정해져 있다. "배열이 엄청 크고 k가 작으면요?" 이 한 마디에 무너지지 않으려면 Heap과 PriorityQueue를 손에 익혀둬야 한다. 이 문서는 HackerRank 스타일의 라이브 면접에서 Heap 계열 문제를 만났을 때, 접근 방식을 말로 설명하고 Java 코드로 구현하고 엣지 케이스까지 커버하는 전 과정을 한 번에 훈련하기 위한 스터디 팩이다.
시니어 백엔드 라이브 코딩에서 Heap/PriorityQueue는 정렬·이분탐색·해시맵 다음으로 가장 자주 나오는 자료구조다. 특히 다음 세 가지 상황에서 반드시 손이 먼저 나가야 한다.
실무 관점에서도 의미가 크다. Top-K는 "전체를 ORDER BY 해서 LIMIT k 할 것인가, 아니면 스트리밍 집계에서 k 크기 힙으로 유지할 것인가"라는 설계 선택으로 그대로 이어진다. 면접관은 알고리즘 문제를 풀면서도 이런 설계 감각을 가진 지원자를 찾는다.
Heap은 부모-자식 관계에 대한 순서 조건만 만족시키는 완전 이진 트리다. 전체 정렬이 아니라 "루트가 항상 최솟값(또는 최댓값)"이라는 약한 조건만 보장한다. 그래서 정렬보다 저렴하다.
contains 남발하면 코드가 느려진다.라이브 코딩에서 "정렬 O(n log n) vs 힙 O(n log k)"를 바로 꺼낼 수 있어야 한다.
기준 정리:
| 상황 | 선택 |
|---|---|
| k = 1, 전체 1회 스캔 | 선형 스캔 |
| k ≪ n, 한 번만 | 크기 k 힙 |
| 전체 정렬 결과가 필요 | 정렬 |
| 스트리밍, 계속 갱신 | 힙 (또는 두 개 힙) |
| k-way merge | 각 스트림의 head를 담는 힙 |
Java PriorityQueue는 기본이 min heap이다. 즉 peek()은 최솟값이다. 이 점이 Top-K 문제에서 가장 흔한 혼동 포인트다.
Java에서 힙을 제어하는 건 99% comparator다. 시그니처는 int compare(a, b)이고 규칙은 단순하다.
a가 먼저(=우선순위 높음=루트에 가까움)b가 먼저즉 "먼저 나와야 하는 걸 '작게' 만들면 된다". min heap으로 동작하기 때문이다.
// 값이 큰 것부터 나오게(=max heap)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
// 빈도 높은 단어 먼저, 동률이면 사전순 먼저
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((a, b) -> {
if (!a.getValue().equals(b.getValue())) {
return Integer.compare(b.getValue(), a.getValue()); // freq desc
}
return a.getKey().compareTo(b.getKey()); // lex asc
});
알고리즘 문제 너머의 쓰임도 같이 떠올릴 수 있어야 면접에서 깊이가 생긴다.
DelayQueue, ScheduledThreadPoolExecutor 내부가 전부 힙 기반이다.이런 사례를 미리 하나씩 붙여두면 "왜 힙을 썼나요?" 질문이 왔을 때 "Top-K 유지 + O(log n) 갱신 비용 + 루트만 보면 되는 구조" 같은 답을 자연스럽게 내놓을 수 있다.
라이브에서 떨어뜨리는 실수들은 거의 이 목록 안에서 나온다.
peek()이 최솟값이라 로직이 완전히 뒤집힌다.(a, b) -> a - b는 a나 b가 음수일 때 오버플로로 부호가 뒤집힐 수 있다. 항상 Integer.compare(a, b)를 쓴다.peek()이고, "가장 큰 k개"는 그 힙 전체다.offer → if (pq.size() > k) pq.poll(); 흐름은 명확하지만, "힙이 비었으면 무조건 넣고, 아니면 루트와 비교"로 쓰면 경계 케이스를 놓치기 쉽다.PriorityQueue는 내부 재정렬을 해주지 않는다.remove(Object) 남용. O(n) 탐색이다. "임의 원소 제거"가 자주 필요하면 힙이 아니라 TreeSet 또는 "lazy deletion + 두 번째 힙" 패턴을 고려해야 한다.Iterator 순서를 정렬 순서로 착각. for (X x : pq)는 순서 보장이 없다. 정렬 순서로 보려면 poll()을 반복해야 한다.HackerRank 스타일은 말하면서 코딩이 기본이다. 다음 6단계 템플릿을 외워두면, 문제를 받자마자 흐름을 선점할 수 있다.
이 흐름은 "코드를 얼마나 빨리 쳤는가"보다 "어떤 근거로 자료구조를 선택했는가"를 보여주기 때문에 시니어 포지션에서 특히 유리하다.
PriorityQueue 자체는 오래된 API지만, record·switch 패턴을 섞어 쓰면 편하다.)javac, java 한 파일로 돌리는 게 가장 빠르다. 라이브 환경을 가정하고 IDE 자동완성 없이 풀어보는 훈련도 최소 일주일에 두 번 한다.실행 루틴 예시:
mkdir -p ~/coding-live/heap && cd ~/coding-live/heap
# 문제 1개당 파일 하나. main에 테스트 케이스를 직접 박아서 실행.
javac TopKFrequent.java && java TopKFrequent
연습 규칙:
PriorityQueue API가 기억나지 않으면 기억나는 만큼만 쓰고 나중에 확인.두 문제 모두 풀이와 Java 전체 코드는 <details> 블록에 숨겨두었다. 먼저 25분 타이머로 직접 풀고, 그다음 펼쳐서 비교한다.
정수 배열 nums와 정수 k가 주어질 때, k번째로 큰 값을 반환하라.
1 <= k <= nums.length <= 10^5, -10^4 <= nums[i] <= 10^4.nums = [3,2,1,5,6,4], k = 2 → 5nums = [3,2,3,1,2,4,5,5,6], k = 4 → 4접근: 전체 정렬은 O(n log n). 대신 크기 k짜리 min heap을 유지한다. 배열을 훑으면서 힙에 값을 넣고, 크기가 k를 넘으면 루트(=현재 k+1개 중 최솟값)를 버린다. 마지막에 힙의 루트가 k번째로 큰 값이다. 복잡도 O(n log k), 공간 O(k).
드라이런 (nums = [3,2,1,5,6,4], k = 2):
자주 하는 실수: max heap에 전부 넣고 k번 poll()하는 것. 답은 맞지만 O(n log n)이라 "정렬이랑 뭐가 다르죠?" 질문에 흔들린다.
import java.util.PriorityQueue;
public class KthLargest {
public static int findKthLargest(int[] nums, int k) {
if (nums == null || k <= 0 || k > nums.length) {
throw new IllegalArgumentException("invalid input");
}
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
if (minHeap.size() < k) {
minHeap.offer(num);
} else if (num > minHeap.peek()) {
minHeap.poll();
minHeap.offer(num);
}
}
return minHeap.peek();
}
public static void main(String[] args) {
System.out.println(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2)); // 5
System.out.println(findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4)); // 4
System.out.println(findKthLargest(new int[]{-1, -2, -3, -4}, 2)); // -2
}
}
문자열 배열 words와 정수 k가 주어질 때, 가장 자주 등장한 단어 k개를 빈도 내림차순으로 반환하라. 빈도가 같으면 사전순 오름차순으로 정렬한다.
1 <= words.length <= 5 * 10^4, 1 <= k <= 고유 단어 수.words = ["i","love","leetcode","i","love","coding"], k = 2 → ["i","love"]words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4 → ["the","is","sunny","day"]접근:
HashMap으로 빈도를 센다. O(n).peek()이 가장 약한 후보(=빈도 작고, 빈도 같으면 단어 큰 쪽)가 되어야 넘치는 순간 루트만 버리면 된다. 즉 comparator가 뒤집힌다.poll()을 반복해 거꾸로 쌓는다. 그래야 빈도 desc / 단어 asc 순서가 된다.복잡도 O(n log k), 공간 O(n + k).
자주 하는 실수:
poll()은 앞을 버린다. 답이 완전히 반대가 된다.Integer.compare로만 쓰고 문자열 비교를 빼먹는 것.poll 순서대로 넣어서 정렬이 거꾸로 나오는 것. Collections.reverse 또는 add(0, x)로 맞춘다.import java.util.*;
public class TopKFrequentWords {
public static List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> freq = new HashMap<>();
for (String w : words) {
freq.merge(w, 1, Integer::sum);
}
// 힙 기준: "약한 것이 위로". 빈도 오름차, 빈도 같으면 단어 내림차.
PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>((a, b) -> {
int freqCmp = Integer.compare(a.getValue(), b.getValue());
if (freqCmp != 0) {
return freqCmp;
}
return b.getKey().compareTo(a.getKey());
});
for (Map.Entry<String, Integer> e : freq.entrySet()) {
heap.offer(e);
if (heap.size() > k) {
heap.poll();
}
}
List<String> result = new ArrayList<>(k);
while (!heap.isEmpty()) {
result.add(heap.poll().getKey());
}
Collections.reverse(result); // 빈도 desc, 단어 asc 순으로 정렬
return result;
}
public static void main(String[] args) {
System.out.println(topKFrequent(
new String[]{"i", "love", "leetcode", "i", "love", "coding"}, 2));
// [i, love]
System.out.println(topKFrequent(
new String[]{"the", "day", "is", "sunny", "the", "the", "the",
"sunny", "is", "is"}, 4));
// [the, is, sunny, day]
}
}
드라이런 포인트 (k = 2, 입력 첫 예시):
{i:2, love:2, leetcode:1, coding:1}i, love만 남는다.poll() 순서는 love → i (약한 순), reverse 후 [i, love]."Heap을 써본 경험이 있나요?"라는 질문은 자료구조 지식을 확인하려는 게 아니라, 언제 쓸지를 판단할 수 있는가를 보려는 것이다. 답변 구조는 다음을 따른다.
PriorityQueue로 씁니다. 기본이 min heap이라 Top-K 문제에선 반대 방향 힙을 쓰는 게 포인트입니다."TreeSet 또는 해시맵 + 힙 조합을 검토합니다."PriorityQueue 기본이 min heap이라는 것을 1초 안에 답할 수 있다.a - b 대신 Integer.compare를 쓴다.offer 후 if size > k poll)을 외워서 쓴다.PriorityQueue의 순회 순서가 정렬 순서가 아니라는 것을 안다.remove(Object)가 O(n)이라는 것을 알고, 잦은 임의 삭제면 다른 자료구조를 고려한다.