[백준] 11279 최대 힙 - Java

문제 - 최대 힙 

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

 

 

 

문제 설명

 

 

입력

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

 

출력

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

 

 

예제 입력

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

 

예제 출력

0
2
1
3
2
1
0
0

---

접근 방법

- 일단 문제를 보면 배열에 자연수를 넣고 배열에서 가장 큰 값을 출력하고 그 값을 제거한다고 했다 

여기에서 어떤 자료구조가 좋을지 생각 해봤을때 가장 큰 값을 출력을 해야할때 그냥 리스트로 하면 가장 큰값을 찾을때 마다 시간이 걸린다

그래서 우선순위 큐를 생각해 보았다 

하지만 우선순위 큐는 가장 작은 숫자가 우선순위가 가장 높다고 판단을 하여 우선순위 큐를 선언할때 Collections.reverseOrder()를 사용 해 주면 되겠다 

 

- 입력에서 0 이 입력 되면 가장 큰 값을 출력하고 그 값을 배열에서 제거하고 만약 배열이 비어 있는 경우는 0을 출력한다

- 자연수가 입력이 되면 그 자연수를 그 배열에 넣는다

---

코드 작성

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    
    public static void main(String[] args) throws IOException {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int N = Integer.parseInt(br.readLine());
            Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
            for (int i = 0; i < N; i++) {
                int calculation = Integer.parseInt(br.readLine());
                if (calculation == 0) {
                    if (queue.isEmpty()) {
                        bw.write(0 + "\n");
                    } else {
                        bw.write(queue.poll() + "\n");
                    }
                } else {
                    queue.offer(calculation);
                }
            }

        }
    }
}

---

문제 풀고 느낀점

 

- 이 문제도 우선순위 큐를 이용하면 쉽고 간단하게 풀 수 있는 문제이다

- 알고리즘 문제를 풀 때 자료구조도 더 공부를 해야 겠다