BOJ 11279

2020-06-14

백준

위 문제는 백준 사이트의 알고리즘 11279 문제에 관한 설명입니다.

문제

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

배열에 자연수 x를 넣는다.
배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다.

다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다.

만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고,

x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다.

입력되는 자연수는 2^31보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다.

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

    static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt( br.readLine() );

        for(int i=0; i<N ;i++){
            int input = Integer.parseInt(br.readLine());

            if(input==0){
                if(!pq.isEmpty()) 
                  System.out.println( pq.poll() );
                else 
                  System.out.println(0);
            }
            else{
                pq.offer(input);
            }
        }
    }
}

해당 문제를 풀기 위해서 알아야하는 것은 우선순위 큐 입니다.

우선순위 큐: 우선순위의 개념을 큐에 도입한 자료 구조로 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.

자료구조 ‘힙(heap)’이란?

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조입니다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이고,

간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말합니다.

이것과 관련해서 잘 정리가 된 사이트를 링크로 같이 올립니다.

자료구조 - 힙이란?

최대힙

« DOM - Node 조작 BOJ 2644 »