[BOJ] 1927번 최소힙
1. 문제
문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
2. 설명
이 문제는 최소 힙을 이용하여 푸는 문제이다. 풀이 자체는 제네릭의 우선순위 큐를 이용하여 해결할 수 있지만 문제 이름 자체가 최소 힙으로, 제네릭을 이용하는 것을 바라는 것 같지 않아 직접 구현하여 해결한다.
3. 풀이
3.1. 구현 방식
최소 힙을 구현에 노드를 직접 연결하여 구현하는 방법도 있지만, 완전 이진 트리의 구조를 가지고 있으므로 배열을 이용하여 구현하였다.
3.2. 노드의 인덱스
배열로 구현하는 이진 트리의 인덱스는 다음과 같다.
- 부모 노드 : (index - 1) / 2
- 자식 노드 1 : index * 2 + 1
- 자식 노드 2 : index * 2 + 2
3.3. 최소 힙의 값 추가 방법
- 가장 마지막 노드에 값을 추가한다.
- 부모 노드와 비교하여 부모 노드의 값이 크면 두 값을 교환한다.
- 커서가 루트에 도달하면 작업을 종료한다.
3.4. 최소 힙의 값 제거 방법
- 가장 위에 있는 값이 가장 작은 값이므로 이 값을 제거한다. (반환을 위하여 임시 공간에 담아둔다.)
- 가장 마지막에 있는 노드를 루트로 이동시킨다.
- 자식 노드 중 가장 작은 값을 값을 찾아 교환한다.
- 커서가 힙의 끝에 도달하면 작업을 종료한다.
4. 구현
4.1. 기본 구조
class MinHeap {
// 배열로 구현
private int[] tree;
private int size;
// 문제에서 명령어의 수가 주어지며 입력되는 데이터의 수는 명령어의 수를 초과하지 않는다.
public MinHeap(int length) {
tree = new int[length];
size = 0;
}
// isEmpty 대신 size를 0과 비교 하는 방법으로 배열이 비어있는지 판단한다.
public int size() {
return size;
}
// 값을 추가하는 메서드
public void add(int value) { /* ... */ }
// 가장 작은 값을 제거하고 반환하는 메서드
public int remove() { /* ... */ }
private int getParent(int idx) {
return (idx - 1) / 2;
}
private void swap(int a, int b) {
int temp = tree[a];
tree[a] = tree[b];
tree[b] = temp;
}
private int firstChild(int idx) {
return idx * 2 + 1;
}
}자바의 큐에서 형태를 따와 add과 remove 메서드를 밖으로 꺼냈으며 isEmpty 대신 size를 이용하게 하였다.
4.2. add 메서드
public void add(int value) {
// 1. 트리의 가장 마지막에 노드를 값을 추가한다.
tree[size] = value;
int current = size++;
// 3. 커서가 루트에 도달하면 작업을 종료한다.
while (current > 0) {
// 2.1. 부모 노드와 비교하여 부모 노드의 값이 크면 두 값을 교환한다.
int parent = getParent(current);
if (tree[parent] > tree[current]) {
swap(parent, current);
current = parent;
} else {
// 2.2. 부모 노드가 현재 값 보다 크면 더 이상 재정렬 할 필요가 없다.
break;
}
}
}4.3. remove 메서드
public int remove() {
// 1.1. 장 위에 있는 값이 가장 작은 값이므로 반환을 위하여 임시 공간에 담아둔다.
int value = tree[0];
// 2. 가장 마지막에 있는 노드를 루트로 이동시킨다.
tree[0] = tree[--size];
int current = 0;
while (true) {
int c1 = firstChild(current);
int c2 = c1 + 1;
int sc = current;
// 3.1. 자식 노드 중 가장 작은 값을 값을 찾는다.
if (c1 < size && tree[current] > tree[c1]) {
sc = c1;
}
if (c2 < size && tree[sc] > tree[c2]) {
sc = c2;
}
//4. 커서가 힙의 끝에 도달하거나 자식 중에 더 작은 값이 없다면 더 이상 재정렬 할 필요 없다.
if (sc == current) {
break;
}
// 3.2. 자식 노드 중 가장 작은 값과 교환한다.
swap(current, sc);
current = sc;
}
// 1.2. 제거한 값을 반환한다.
return value;
}5. 문제 풀이
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
MinHeap mh = new MinHeap(n);
for (int i = 0; i < n; i++) {
int input = Integer.parseInt(br.readLine());
if (input == 0) {
if (mh.size() > 0) {
bw.write(mh.remove() + "\n");
} else {
bw.write("0\n");
}
} else {
mh.add(input);
}
}
bw.flush();
bw.close();
br.close();
}문제는 간단히 명령어의 수를 입력 받고 0이면 힙의 내용을 출력, 0이 아니면 힙에 값을 추가하는 방법으로 해결할 수 있다.
즉, 이 문제는 최소 힙이 구현 된다면 간단히 풀리는 문제이다.
6. 마무리
나는 한동안 java 사용법을 익히기 위하여 가급적 제네릭이나 내장 함수들을 이용했다. 하지만 이 문제 자체의 목적이 힙을 직접 구현하는 것을 바라는 것 같아 힙을 구현해보았다.
직접 이런 부분까지 구현하는 것은 아주 오랜만이라 실수가 잦았지만 약간이나마 머리를 다시 굴리는 듯하여 문제를 풀고 후련한 기분이 들었다.
