문제
N개의 연산을 처리하는 최솟값 우선순위 큐(Min-Heap) 구현 문제다. 양의 정수 x가 입력되면 힙에 삽입하고, 0이 입력되면 최솟값을 삭제·출력(힙이 비어있으면 0 출력)한다. 라이브러리를 사용하지 않고 배열 기반 힙을 직접 구현하여 삽입과 삭제의 원리를 이해하는 문제다.
입력
- 첫째 줄: 연산 수 N (1 이상 100,000 이하)
- 둘째 줄부터 N개 줄: 연산 값 (0이면 최솟값 출력, 양수면 삽입)
출력
0 연산마다 최솟값을 한 줄씩 출력한다. 힙이 비어있으면 0을 출력한다.
예제
| 입력 | 출력 |
|---|---|
9 0 12345678 1 2 0 0 0 0 32 | 0 1 2 12345678 32 |
풀이
배열 기반의 완전 이진 트리를 이용하여 최소 힙을 직접 구현한다.
- 삽입(
add): 배열 끝에 값을 추가하고 부모와 비교하면서 위로 swap(sift-up) - 삭제(
delete): 루트(최솟값)를 꺼내고 마지막 원소를 루트로 올린 뒤 자식과 비교하며 아래로 swap(sift-down) - sift-down 시 두 자식 중 더 작은 쪽과 비교하여 교환 — 범위 초과 방지를 위해
get()함수로 안전하게 접근 - 빈 힙에서 삭제 연산 시 0을 출력
핵심 아이디어: 배열의 인덱스 관계(부모: i/2, 자식: i*2, i*2+1)를 이용하면 힙을 추가 포인터 없이 구현할 수 있으며, 삽입·삭제 모두 O(log N)이 보장된다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Day124BOJ1927최소힙구현 {
static int[] heap;
static int idx;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int N;
N = Integer.parseInt(br.readLine());
heap = new int[N * 4];
idx = 0;
while (N-- > 0) {
int num = Integer.parseInt(br.readLine());
if (num > 0) {
add(num);
} else {
bw.write(delete() + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
public static void add(int num) {
heap[++idx] = num;
int numIdx = idx;
while (numIdx != 0)
if (heap[numIdx] < heap[numIdx / 2]) {
swap(numIdx, numIdx / 2);
numIdx /= 2;
} else
break;
}
public static int delete() {
if (idx == 0)
return 0;
int min = heap[1];
heap[1] = heap[idx];
heap[idx] = 0;
int tmp = 1;
--idx;
while (tmp <= idx) {
int childNode = (get(tmp * 2) > get(tmp * 2 + 1)) ? tmp * 2 + 1 : tmp * 2;
if (heap[tmp] > get(childNode)) {
swap(tmp, childNode);
tmp = childNode;
} else {
break;
}
}
return min;
}
public static void swap(int idx1, int idx2) {
int tmp = heap[idx1];
heap[idx1] = heap[idx2];
heap[idx2] = tmp;
}
public static int get(int index) {
if (index > idx)
return Integer.MAX_VALUE;
else
return heap[index];
}
}복잡도
- 시간: O(N log N) — N번의 연산 각각 O(log N)
- 공간: O(N) — 힙 배열