[JAVA 알고리즘]BAEKJOON 11279번 최대 힙

최대 힙

---

문제 설명

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

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

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

제한사항

•  없음

입력

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

출력

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

입출력 예

answers	return
13 0 1 2 0 0 3 2 1 0 0 0 0 0	0 2 1 3 2 1 0 0

---

나의 문제풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

        int x = Integer.parseInt(br.readLine());

        for (int i = 0; i < x; i++) {
            int temp = Integer.parseInt(br.readLine());
            if (temp > 0) {
                queue.add(temp);
            } else {
                if (!queue.isEmpty()) {
                    bw.write(queue.poll() + "\n");
                } else {
                    bw.write("0\n");
                }
            }
        }
        bw.flush();
        bw.close();
    }
}

• PriorityQueue를 이용해서 우선순위 큐를 선언해준다.
• 객체 생성시  Collections.reverseorder()을 이용해서 높은 수 우선으로 설정한다. (없으면 낮은 수 우선)
• 첫 줄의 연산의 개수 만큼 for문을 반복한다.
• 입력의 자연수가 0보다 크면 큐에 자연수를 넣어준다.
• 자연수가 0일 경우 큐에 수가 존재할 경우 큐에서 앞의 수를 빼내면서 출력 아닐경우 0을 출력한다.

---

느낀 점

처음에는 우선순위 큐의 형태로 직접 구현해서 해보았는데 테스트에서는 값이 잘 나오는데 제출을 할 경우 시간 초과로 인해서 실패하였다. 찾아보니 자바에서는 PriorityQueue를 이용해서 간단하게 사용할 수 있었다..이럴수가..

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayList<Integer> list = new ArrayList<>();

        int x = Integer.parseInt(br.readLine());

        list.add(0);
        for (int i = 0; i < x; i++) {
            int temp = Integer.parseInt(br.readLine());
            if (temp > 0) {
                int cur = list.size();
                list.add(temp);
                int parent = cur / 2;
                while (parent > 0) {
                    if (list.get(cur) > list.get(parent)) {
                        list.add(parent, list.remove(cur)); // 가장 큰수가 앞으로 온다.
                    }
                    cur = parent;
                    parent = cur / 2;
                }
            } else {
                if (list.size() > 1) {
                    bw.write(list.remove(1) + "\n");
                } else {
                    bw.write("0\n");
                }
            }
        }
        bw.flush();
        bw.close();
    }
}