문제
정수를 하나씩 입력받을 때마다, 지금까지 입력된 수들의 중앙값(중간값)을 출력하는 문제이다. 입력된 수의 개수가 짝수일 때는 중앙값 중 작은 것을 출력한다. 최대 100,000개의 수가 입력된다.
입력
- 첫째 줄: 수의 개수 N (1 이상 100,000 이하)
- 다음 N줄: 정수 (절댓값 10,000 이하)
출력
- N줄: 매 수를 입력받은 후의 중앙값
예제
| 입력 | 출력 |
|---|---|
7 1 5 2 10 -99 7 5 | 1 1 2 2 1 2 2 |
풀이
두 개의 힙(최대 힙 + 최소 힙)으로 스트리밍 중앙값을 O(N log N)에 구한다. 최대 힙(max)은 중앙값 이하의 수를, 최소 힙(min)은 중앙값 초과의 수를 저장한다.
max(최대 힙): 하위 절반,min(최소 힙): 상위 절반을 저장한다.max.size() == min.size()이면max에, 아니면min에 새 수를 삽입한다. 이렇게 하면 max 크기가 항상 min 이상이 된다.- 삽입 후
min.peek() < max.peek()이면 두 힙의 루트를 교환한다. - 중앙값은 항상
max.peek()이다.
핵심 아이디어: 중앙값 기준으로 작은 절반은 최대 힙, 큰 절반은 최소 힙에 유지한다. 두 힙의 크기 차이가 1 이내가 되도록 균형을 맞추면, 항상 최대 힙의 루트가 중앙값이 된다. 힙 교환 조건으로 최대 힙 루트가 최소 힙 루트보다 크지 않도록 보장한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class Day107BOJ1655가운데힙 { // 1655 가운데 힙
static int N;
static PriorityQueue<Integer> min, max;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
min = new PriorityQueue<>((o1, o2) -> o1 - o2);
max = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(br.readLine());
if (min.size() == max.size())
max.offer(num);
else
min.offer(num);
if (!min.isEmpty() && !max.isEmpty())
if (min.peek() < max.peek()) {
int tmp = min.poll();
min.offer(max.poll());
max.offer(tmp);
}
sb.append(max.peek() + "\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N log N) — 각 삽입/삭제가 O(log N)
- 공간: O(N)