[코테] 백준 1927번 : 최소 힙 (java)

https://www.acmicpc.net/problem/1927

알고리즘 분류 : 자료 구조, 우선순위 큐

직접 힙을 구현하여 풀이하였습니다.

 

❓문제

---

🔅해석

직접 힙을 구현하여 풀어본 문제이다.

 

최소 힙은 ' 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다.'는 힙 조건을 가진다.

힙 조건에 맞춰 삽입과 삭제 연산을 진행한다.

 

삽입 연산

1. 트리의 가장 마지막 위치에 노드를 삽입한다.
2. 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.
3. 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.
4. 조건에 만족하거나 추가된 노드가 루트에 도달할 때까지 2 ~ 3을 반복한다.

 

123 먼저 삽입 후 1 삽입

2 삽입

2 삽입 후 정렬된 모습

 

입력을 받다가 '0'을 만나게 되면 삭제 연산을 수행한다.

 

삭제 연산

1. 힙의 삭제 연산은 항상 루트 노드를 삭제한다.
2. 트리의 가장 마지막 노드를 루트 자리로 삽입한다.
3. 바꾼 위치의 노드가 힙 조건을 만족하는지 확인한다.
4. 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.
5. 조건을 만족하거나 리프 노드에 도달할 때까지 3 ~ 4를 반복한다.

삭제

 

 

힙을 직접 구현하는 문제는 많지 않지만, 힙의 이해를 위해 풀어보기 좋은 문제인 것 같다.

---

⭕정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		MinHeap minheap = new MinHeap();

		for (int i = 0; i < N; i++) {
			int num = Integer.parseInt(br.readLine());

			if (num == 0) {
				if (minheap.list.size() <= 1) {
					sb.append(0).append("\n");
				} else {
					sb.append(minheap.delete()).append("\n");
				}
			} else {
				minheap.insert(num);
			}
		}

		System.out.println(sb);
		br.close();
	}

}

class MinHeap {
	List<Integer> list;

	public MinHeap() {
		list = new ArrayList<>();
		list.add(0);
	}

	public void insert(int val) {
		list.add(val);

		int current = list.size() - 1;
		int parent = current / 2;

		while (true) {
			if (parent == 0 || list.get(parent) <= list.get(current)) {
				break;
			}

			int temp = list.get(parent);
			list.set(parent, list.get(current));
			list.set(current, temp);

			current = parent;
			parent = current / 2;
		}
	}

	public int delete() {
		int top = list.get(1);
		list.set(1, list.get(list.size() - 1));
		list.remove(list.size() - 1);

		int currentPos = 1;
		while (true) {
			int leftPos = currentPos * 2;
			int rightPos = currentPos * 2 + 1;

			if (leftPos >= list.size()) {
				break;
			}

			int minValue = list.get(leftPos);
			int minPos = leftPos;

			if (rightPos < list.size() && minValue > list.get(rightPos)) {
				minValue = list.get(rightPos);
				minPos = rightPos;
			}

			if (list.get(currentPos) > minValue) {
				int temp = list.get(currentPos);
				list.set(currentPos, list.get(minPos));
				list.set(minPos, temp);
				currentPos = minPos;
			} else {
				break;
			}
		}
		return top;
	}
}

 

---

❗결과