[백준 11279] 우선순위 큐 + Comparator - java(자바) 최대 힙

최대 힙

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입력 1

13
0
1
2
0
0
3
2
1
0
0
0
0
0

예제 출력 1

0
2
1
3
2
1
0
0

---

java 코드

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

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

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

 

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

 

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

 

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

 

우선순위의 기본 값은 최소 입니다.

그러나 최대로 하려면 정반대인 new PriorityQueue<Integer>(Collections.reverseOrder()); 이렇게 하면 됩니다.

 

그러나 이 어느문제는 풀기위해서 우선순위 기준을 자유자재로 하려면 어떻게 할까요?

Comparator 클래스를 임의로 만들면 됩니다.

저는 MyReverseIntComparator로 이름을 지었습니다.

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException   {
        final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());// 1~n
        int input;
        // 인자에 Comparator를 넣는데, 스스로 MyReverseIntComparator 라는 클래스를 만들어서 했습니다.
        MyReverseIntComparator maxComparator = new MyReverseIntComparator();
        PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(maxComparator);
        ///////////////////////////////////////////////////////////////////////////////
        // 단순히 최대 큐면, 정렬을 정반대로 하면 되므로 아래 처럼 입력해서 클래스 생성없이 가능
        //PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            input = Integer.parseInt(br.readLine());
            if (input>0) {
                maxQueue.add(input);
            } else {
                if (!maxQueue.isEmpty()) {
                    System.out.println(maxQueue.poll());
                }
                else{
                    System.out.println(0);
                }
            }
        }
        br.close();
    }

}

// 우선순위 비교 클래스 생성
class MyReverseIntComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        if ((int) o1 > (int) o2) {
            return -1;
        }
        else if((int) o1 < (int) o2) {
            return 1;
        }
        else{
            return 0;
        }
    }
}

---

보시는것 처럼, Comparator 클래스를 상속받아서 compare메소드를 오버라이딩 시켜주면 됩니다!!

아래는 최대값이 우선적으로 나오도록 한것입니다.

class 아무이름 implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        if ((int) o1 > (int) o2) {
            return -1;
        }
        else if((int) o1 < (int) o2) {
            return 1;
        }
        else{
            return 0;
        }
    }
}

---

우선순위 큐(힙) 활용

Priority Queue 선언

선언할때 인자로 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에 첫번째 값 참조(최소값 출력)

---

comparator 클래스 이용하기

최소 힙(원본)의 본래의 메소드 입니다. 숫자가 작은것을 우선순위로 하죠.

이 내용을 조금 변형해서 우선순위와 정렬 기준을 설정할수 있습니다.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                if(o1 < o2) {
                    return -1;
                }else if(o1 > o2) {
                    return 1;
                }else {
                    return 0;
                }
            }
        });