[백준 1927] 우선순위 큐 java(자바) - 최소 힙

최소 힙

문제

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

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  

---

java 코드

이 문제는 우선순위 큐를 사용하는 문제입니다.

일반적인 큐(Queue)는 First in-First Out 구조로, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조였습니다.

하지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것 것을 말합니다.

우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있기 때문에 이 둘을 묶어서 표현하곤 합니다.

 

우선순위 큐를 활용하는 법은 아래에 설명합니다.

 

백준의 제한 시간에 빠듯해서, scanner 말고 buffered reader를 이용해서 시간을 1초정도로 단축했습니다.

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException   {
        // Scanner scan = new Scanner(System.in);
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());// 1~n

        int input;
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>();
        for (int i = 0; i < n; i++) {
            input = Integer.parseInt(br.readLine());
            if (input>0) {
                minQueue.add(input);
            } else {
                if (!minQueue.isEmpty()) {
                    System.out.println(minQueue.poll());
                }
                else{
                    System.out.println(0);
                }
            }
        }
        br.close();
    }
}

---

우선순위 큐(힙) 활용

 

Priority Queue 선언

선언할때 인자로 Comparator 클래스를 넣어서 우선순위의 기준을 설정할수 있습니다.

그러나 기본값이 최소이므로 이 문제는 Comparator없이 풀수 있으므로 생략하겠습니다.

다음 포스트인 최대힙 , 절대값힙 문제에서 사용법을 올리겠습니다.

import java.util.PriorityQueue; //import

//정수형 priorityQueue 선언 (우선순위가 낮은 숫자 순) 최소힙
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//정수형 priorityQueue 선언 (우선순위가 높은 숫자 순) 최대힙
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

Priority Queue 값 추가

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.offer(2);   // priorityQueue 값 2 추가

 

Priority Queue 삭제

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

 

Priority Queue 출력

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.peek();       // priorityQueue에 첫번째 값 참조(최소값 출력)

---