11279번: 최대 힙 [JAVA]

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

11279번: 최대 힙

 

접근 방식)

1. 내림차순으로 정렬하는 우선순위 큐를 만든다.

2. 조건에 맞게 분기해서 큐에 넣고, 빼고, 값 출력하도록 해준다.

    

 

두 가지 방식으로 풀었었는데, 입력+우선순위큐 정렬 정의 + 조건 분기하는 쪽에 약간의 차이만 있다.

1) Scanner,  Collections.reverseOrder()

package tony_git.data_structure2;

import java.util.*;
public class B_11279 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            int n = sc.nextInt();
            if (n == 0 && pq.isEmpty()) {
                sb.append(0).append('\n');
                continue;
            } else if (n == 0)
                sb.append(pq.poll()).append('\n');
            else
                pq.add(n);
        }
        System.out.println(sb);
    }
}

 

 

2) BufferedReader, 우선순위큐 정렬 정의

import java.io.*;
import java.util.*;
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<>((o1, o2) -> {
            return o2 - o1;
        });

        for (int i = 0; i < N; i++) {
            int request = Integer.parseInt(br.readLine());
            if (request == 0) {
                if (pq.isEmpty())
                    sb.append("0").append("\n");
                else
                    sb.append(pq.poll()).append("\n");
            } else
                pq.add(request);
        }
        System.out.println(sb.toString());
    }    
}