[백준] 최소 힙 : 1927 - 우선순위 큐 (S2)

1.  💎 문제

1927번: 최소 힙

 

 

 

2.  🤔어떻게 풀까

저번에 풀어봤던 문제랑 비슷해서 그때 처럼 `TreeMap`을 써서 풀기로 했다.

조건은 가장 작은 수를 단 번에 꺼낼 수 있어야 한다는 것과 중복값을 포함할 수 있어야 한다는 것이다.

가장 작은 수를 앞에서 꺼내기 위해 정렬을 한 후 넣으면 시간 초과가 난다.

 TreeSet 또는 TreeMap

삽입과 동시에 정렬을 해서 넣어준다. 이진 탐색으로 구현되어 있다.

-정렬 방법 변경-
생성할 때 Compartor를 넣어주어 원하는 정렬을 할 수 있다.
TreeSet<Integer> ts1 = new TreeSet<>(Comparator.reverseOrder())

 

 

구현 코드는 아래와 같다.

문제는 맞췄지만, 너무 1100ms라는 너무 많은 시간이 걸렸다. 그래서 시간이 짧은 다른 사람의 코드를 보았다.

class Main {

    static final int MIN = 0;
    static final int MAX = 100_000;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 연산의 개수
        int N = Integer.parseInt(br.readLine());
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();

        for(int i =0; i<N; i++){
            int num = Integer.parseInt(br.readLine());
            // 가장 작은 값 출력
            if(num == 0) {
                try {
                    int key = treeMap.firstEntry().getKey();
                    int value = treeMap.firstEntry().getValue();
                    if (value > 1) {
                        treeMap.replace(key, value - 1);
                    } else {
                        treeMap.remove(key);
                    }
                    bw.write(key + "\n");
                } catch (IllegalStateException e) {
                    bw.write(0 + "\n");
                } catch (NullPointerException e){
                    bw.write(0 + "\n");
                }
                continue;
            }
            // 요소 추가
            int value = treeMap.getOrDefault(num, 0) +1;
            treeMap.put(num, value);
        }
        bw.flush();

        bw.close();
        br.close();
    }


}

 

 

 

3.  또 다른 방법 : 우선 순위 큐 이용

바로 우선 순위 큐를 이용한 방법이다. 

우선순위 큐(PriorityQueue)

중복을 포함하여, 낮은 수를 가장 높은 기준으로 삽입한다.
생성할 때 매개변수로 Comprator를 넣어 정렬 기준을 바꿀 수 있다.

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

 

문제의 조건대로 이미 구현되어 있기 때문에, 큐가 비어있을 때 적절한 처리만 해주면 된다.

코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {

    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 연산의 개수
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for(int i =0; i<N; i++){
            int num = Integer.parseInt(br.readLine());
            // 가장 작은 값 출력
            if(num == 0) {
                if(pq.isEmpty()){
                    bw.write(0+"\n");
                }else{
                    bw.write(pq.poll()+"\n");
                }
                continue;
            }
            // 요소 추가
            pq.add(num);
        }
        bw.flush();

        bw.close();
        br.close();
    }


}

 

시간은 376ms로 약 800ms나 줄었다.