[BOJ/Java] #11279 최대 힙 - PriorityQueue

알고리즘 분류

- 자료 구조

- 우선순위 큐

 

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

 

N개의 줄에 정수 x가 주어진다. (1<=N<=100,000)

x가 자연수라면 배열에 x라는 값을 넣고,

x가 0이라면 배열에서 가장 큰 값을 출력, 그 값을 배열에서 제거한다.

배열이 비어있는 경우 가장 큰 값을 출력하라고 하면 0을 출력한다.

 

먼저 내가 처음 생각했던 방법은

ArrayList를 선언하고,

x가 자연수라면 add,

x가 0이라면 Collections.max()로 max 값을 찾아 출력 및 제거하는 거였다.

ArrayList 사용 (실패 코드)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int cal = Integer.parseInt(br.readLine());
            if (cal == 0) {
                if (list.size() == 0) {
                    sb.append("0\n");
                } else {
                    int max = Collections.max(list);
                    sb.append(max).append("\n");
                    list.remove(list.indexOf(max));
                }
            } else {
                list.add(cal);
            }
        }

        System.out.println(sb);
    }
}

 

그러나 이 방법은 Collections.max()와 list.remove()가 각각

O(N)의 시간 복잡도를 가지기 때문에

전체적으로 O(N^2)가 되어 10^10 즉 1초를 넘게 된다.

 

방법을 알아보니

PriorityQueue를 사용하는 문제였고, 이를 사용하니 아주 쉽게 풀었다.

PriorityQueue 사용 (성공 코드)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < N; i++) {
            int cal = Integer.parseInt(br.readLine());
            if (cal == 0) {
                if (pq.isEmpty()) {
                    sb.append("0\n");
                } else {
                    sb.append(pq.poll()).append("\n");
                }
            } else {
                pq.offer(cal);
            }
        }

        System.out.println(sb);
    }
}

 

이 기회에 PriorityQueue에 대해 정리하고자 한다.

 

PriorityQueue

우선순위 큐

일반적인 큐의 구조 FIFO(First In First Out)를 가지면서,

데이터가 들어온 순서대로 데이터가 나가는 것이 아닌,

우선순위를 먼저 결정하고 그 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

 

int, String, Double과 같은 기본 타입은 Comparable을 이미 구현하고 있어서

그냥 PriorityQueue에 넣어도 우선순위가 자동으로 정해진다.

 

그러나 직접 만든 클래스에서 PriorityQueue를 사용하기 위해서는

우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야 한다.

Comparable Interface를 구현하면 compareTo method를 override 하게 되고,

해당 객체에서 처리할 우선순위 조건을 리턴해주면

PriorityQueue가 알아서 우선순위가 높은 객체를 추출해준다.

class Task implements Comparable<Task> {
    int priority;
    String name;

    public Task(int priority, String name) {
        this.priority = priority;
        this.name = name;
    }

    // compareTo를 override해서 우선순위 기준을 정의
    @Override
    public int compareTo(Task other) {
        // priority가 클수록 우선순위 높게 하고 싶다면 (MaxHeap처럼)
        return other.priority - this.priority;
    }
}

 

PriorityQueue<Task> pq = new PriorityQueue<>();
pq.add(new Task(3, "A"));
pq.add(new Task(5, "B"));
pq.add(new Task(1, "C"));

System.out.println(pq.poll().name); // "B"

 

내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.

내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(logN)이다.

 

import java.util.*;

// 낮은 숫자가 우선 순위인 int형 우선순위 큐
// 최소힙(Min Heap)
PriorityQueue<Integer> pqLowest = new PriorityQueue<>();

// 높은 숫자가 우선 순위인 int형 우선순위 큐
// 최대힙(Max Heap)
PriorityQueue<Integer> pqHighest = new PriorityQueue<>(Collections.reverseOrder());