백준 1927번 : 최소 힙

1. 문제

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

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

예제 입력 1 복사

9
0
12345678
1
2
0
0
0
0
32

 

예제 출력 1 복사

0
1
2
12345678
0

2. 코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		List<Long> list = new ArrayList<>();
		for (int i = 0; i < T; i++) {
			long input = Long.parseLong(br.readLine());
			if (input == 0) {
				if (list.isEmpty()) {
					sb.append(0).append("\n");
				} else {
					Collections.sort(list);
					sb.append(list.get(0)).append("\n");
					list.remove(0);
				}
			} else {
				list.add(input);
			}
		}
		System.out.println(sb);
	}
	
}

3. 해설

• 출력할 때 매번 정렬시켜서 최소값을 출력하고 삭제까지 진행
  → 매우 매우 비효율적, 시간이 너무 오래걸림

4. 다른 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		PriorityQueue<Long> list = new PriorityQueue<>();
		for (int i = 0; i < T; i++) {
			long input = Long.parseLong(br.readLine());
			if (input == 0) {
				if (list.isEmpty()) {
					sb.append(0).append("\n");
				} else {
					sb.append(list.poll()).append("\n");
				}
			} else {
				list.add(input);
			}
		}
		System.out.println(sb);
	}
	
}

• List 자료 구조 대신 PriorityQueue를 활용
• PriorityQueue는 poll() 과 peek()이 최솟값을 반환하도록 하는 자료구조

5. PriorityQueue 테스트

import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	public static void main(String[] args) {
		Queue<Integer> queue = new PriorityQueue<>();
		queue.add(9);
		System.out.println(queue);
		queue.add(1);
		System.out.println(queue);
		queue.add(3);
		System.out.println(queue);
		queue.add(2);
		System.out.println(queue);
		queue.add(4);
		System.out.println(queue);
		queue.add(7);
		System.out.println(queue);
		queue.add(8);
		System.out.println(queue);
		queue.add(5);
		System.out.println(queue);
		queue.add(6);
		System.out.println(queue);
		System.out.println("===========================================");
		while (!queue.isEmpty()) {
            System.out.print(queue.poll() + " ");
        }
	}
}

• 1 ~ 9 까지 숫자를 무작위 순서로 입력을 하고 그때 그때 어떤 순서인지 출력해서 확인을 하면

[9]
[1, 9]
[1, 9, 3]
[1, 2, 3, 9]
[1, 2, 3, 9, 4]
[1, 2, 3, 9, 4, 7]
[1, 2, 3, 9, 4, 7, 8]
[1, 2, 3, 5, 4, 7, 8, 9]
[1, 2, 3, 5, 4, 7, 8, 9, 6]

• 완전히 깔끔하게 정렬된 형태는 아니지만 어쨋든 최소값이 제일 앞에 있음을 확인 할 수 있고
• 반복문을 통해 poll()을 뽑아보면 최종적으로

[9]
[1, 9]
[1, 9, 3]
[1, 2, 3, 9]
[1, 2, 3, 9, 4]
[1, 2, 3, 9, 4, 7]
[1, 2, 3, 9, 4, 7, 8]
[1, 2, 3, 5, 4, 7, 8, 9]
[1, 2, 3, 5, 4, 7, 8, 9, 6]
===========================================
1 2 3 4 5 6 7 8 9

• 최솟값만을 반환해서 순서대로 반환된 것을 확인 할 수 있다.