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

풀이 방법

이 문제는 Priority Queue 라는 것을 알 수 있는 좋은 문제라고 생각합니다. 문제를 읽어보았을 때 그냥, Queue를 이용해서 풀면 될 것 같다는 생각을 하고 문제를 풀었으나, 큐의 특성상 선입선출 즉, 먼저 들어온 것이 큐의 대기열에 있다가 먼저 나가므로 문제에서 원하는 작은 수가 먼저 출력되는 부분을 만족하지 않았습니다.

이 부분을 해결하기 위해서는 정렬이 필요한데, 정렬하는 부분을 따로 구현을 해줘야 합니다. 그래서 저는 이 방법 말고 분명히 자바에서 제공하는 자료구조 중에서 사용할 수 있는 것이 있다고 판단했습니다. 그리고 C++ 코드에서는 Priority Queue라는 것을 사용하는 것을 보아 자바에서도 비슷한 것이 있을 것이라고 추측했고, 그 추측은 정답이었습니다 :)

이 문제를 풀 때는 Priority Queue의 natural ordering 속성을 통해서 문제를 해결하였습니다. Priority Queue는 natural ordering에 따라서 큐를 정렬합니다. 한마디로 오름차순으로 큐를 정렬시킨다는 뜻입니다. 이러한 속성을 이용해서 작은 값이 먼저 출력될 수 있도록 문제를 풀 수 있었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.io.*;
import java.util.*;

public class BOJ1927 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        int N = Integer.parseInt(bf.readLine());
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(bf.readLine());
            if (x == 0) {
                if (!priorityQueue.isEmpty())
                    bw.write(priorityQueue.poll() + "\n");
                else
                    bw.write(0 + "\n");
            } else {
                priorityQueue.add(x);
            }
        }


        bw.flush();
        bw.close();

    }

}

배운 점

이 문제를 풀면서 배운 점은 Priority Queue라는 자료구조에 대해서 배우게 된 것입니다. 이 자료구조의 특성과 성질을 공부해볼 수 있었습니다.

먼저, 일반적인 큐(Queue)는 선입선출(FIFO)의 구조를 가집니다. 그렇다면 Priority Queue는 어떻게 다를까요??

Priority Queue는 내부적으로 Natural Ordering에 따라서 정렬하는 큐입니다. 그래서 다음의 코드를 테스트해보면 10이라는 숫자가 나와야 하는데, 실제로 1이 나오는 것을 확인할 수 있습니다.

또한, 무작위로 숫자 값을 넣었을 경우에는 어떻게 될까요??? 이 경우에 오름차순된 상태로 출력되는 것을 확인 할 수 있습니다. 이것이 가장 큰 Priority Queue의 특징입니다. 그리고 Priority Queue는 null을 허용하지 않습니다. 왜냐하면 Natural Ordering에 기반을 두고 있기 때문에 정렬할 수 없는 null은 허용되지 않는 것입니다.

Priority Queue의 head는 가장 적은 값이 나옵니다. 만약 다수의 엘리먼트가 가장 적은 값이라면, 그 헤드는 그 중에 하나가 되는데 어떤것이 될지는 모릅니다.

우선 순위 대기열에는 각 요소에 우선순위가 할당되어 있습니다. 우선 순위가 가장 높은 요소가 대기열 맨 위에 나타납니다. 이제는 각 요소에 우선 순위를 지정하는 방법에 따라 다릅니다. 그렇게 하지 않으면 Java가 기본 방식으로 처리합니다. 기본 방식은 가장 값이 작은 요소에 가장 높은 우선 순위가 할당되므로 먼저 큐에서 제거됩니다. 동일한 우선 순위를 가진 요소가 여러 개 있으면 타이는 임의로 끊어집니다.

또한, 생성자 PriorityQueue(initialCapacity, comparator)에서 comparator를 사용하여 순서를 지정할 수도 있습니다.

Method

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

PriorityQueue<Integer> pQueue = new PriorityQueue<>();
for(int i=0;i<=10;i++){
    pQueue.add(i);
}
System.out.println("result : "+pQueue.peek());
// 마지막 삽입된 요소 참조!

PriorityQueue<Integer> pQueue2 = new PriorityQueue<>();
pQueue2.add(6);
pQueue2.add(11);
pQueue2.add(3);
pQueue2.add(12);

int count = pQueue2.size();
for(int i=0;i<count;i++)}{
    System.out.println(pQueue2.poll());
}