[백준 11279 : JAVA] 최대 힙 / PriorityQueue

개요

 

priorityqueue 자료구조를 이용하여 푸는 문제이다.

 

기존의 queue는 [FIFO] 구조로 First In First Out 구조를 가지고 있다.

식당에 밥을 먹기 위해 가서 줄을 섰을 때 맨 처음 줄을 선 사람이 맨 처음으로 식당에 들어가는 것과 같이

입력이 10 20 30 40 50 이 있을 때 출력도 10 20 30 40 50 이 된다고 생각하면 된다.

따라서 stack [LIFO] 과는 반대의 개념이라고 볼 수 있다.

 

priorityqueue는 queue 구조와 비슷하게 생각할 수 있고, 이름처럼 우선순위 큐이다.

queue는 First In First Out이라면 priorityqueue는 Comparator 인터페이스의 compare 메소드를 오버라이딩 한 코드에 따라 우선순위가 정해지고 그 우선순위가 가장 높은 것부터 출력이 된다.

 

따라서 이 문제에서는 우선순위를 입력된 자연수의 크기순으로 잡으면 풀이가 가능하다.

 

문제

 

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

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

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

 

입력

 

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

 

풀이

 

이 문제는 JAVA를 사용할 경우 PriorityQueue 클래스를 사용하면 간단한 풀이가 가능하다.

Comparator 인터페이스의 compare 메서드만 오버라이딩한다면 별다른 작업 없이 풀 수 있다.

하지만, 나는 클래스를 따로 작성하여 내부적으로 입력된 값들을 sorting 해서 저장하고 문제의 요구대로 가장 큰 값을 반환하는 메소드를 작성하였다.

 

그 이유는 PriorityQueue 클래스 내부적으로 우선순위대로 값들을 sorting 하여 저장하고 가장 끝의 값을 출력해주는 줄 알았지만 그런 방식은 아니었다.

왜냐하면 poll 메소드가 아닌 Iterator인터페이스를 통해 PriorityQueue의 값들을 출력해 봤을 때 값들이 sorting이 되어 있지 않았기 때문이다.

 

궁금증이 생겨 PriorityQueue 클래스 코드를 까 봤는데 내가 생각한 방식은 아니었다.

 

 

코드

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

class MyHip{
    List<Integer> list;
    int size;

    public MyHip(){
        list = new ArrayList<>();
        size = 0;
    }

    public void operation(int x){
        if(x != 0){
            add(x);
        }else if(size == 0 && x == 0){
            System.out.println("0");
        }else{
            System.out.println(list.remove(size - 1));
            size--;
        }
    }

    public void add(int x){
        int left = 0;
        int right = list.size() - 1;

        while(left <= right){
            int mid = (left + right) >> 1;

            if(list.get(mid) >= x){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        list.add(left, x);
        size++;
    }
}
public class Backjoon11279 {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        MyHip myHip = new MyHip();

        for(int i = 0 ; i < n; i++){
            int value = Integer.parseInt(br.readLine());
            myHip.operation(value);
        }
    }
}