[24/11/04] 우선순위 큐

11286

우선순위 큐만 알면 쉽게 풀리는 문제이다.

그러기에 우선순위 큐를 알아보자.

 

일반적인 큐는 FIFO의 구조로 오로지 들어간 순서에만 영향을 받는다. 따라서 이미 들어간 순간 내가 임의로 순서 조작을 하지는 못한다. 내가 어떤 순서로 큐로 넣었던 간에 큐 내부에서 우선순위를 정하여 다시 정렬하여 그 우선순위에 맞게 큐에서 순서대로 빼는 것을 우선순위 큐라고 한다.

 

따라서 해당 문제는 우선순위 큐가 없었다면 매번 뺄때마다 리스트 원소를 전부 보고 작은 순서대로 빼야되기에 이미 O(N)이 걸리고 그것을 n번 해야되기에 O(N^2)이 걸려 타임아웃이다.

우선순위 큐

그러면 우선순위 큐에서 우선순위를 어떻게 지정할것이냐? 우선순위 큐에서는 우선순위가 높은 것을 차례로 poll 시킨다.

Comparator 를 통해서 임의적으로 순서를 내가 직접 정해줘야한다.

Comparator는 람다식(함수형 인터페이스)를 통해 익명 클래스를 통한 인스턴스를 만들어서 인자로 넣어주면 된다.

 

양수를 리턴한다면 매개변수의 순서를 뒤집고, 음수를 리턴한다면 매개변수 순서 그대로 간다.

이를 우선순위로 적용하면 뒤쪽에 있을수록 우선순위가 낮고, 앞쪽에 있을수록 우선순위가 높다.

 

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

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2) -> {
            int first_abs = Math.abs(o1);
            int second_abs = Math.abs(o2);
            if(first_abs==second_abs){
                return o1>o2?1:-1; 
            }
            return first_abs-second_abs;
        } );
        for(int i=0; i<n; i++){
            int num = Integer.parseInt(bf.readLine());
            if(num!=0){
                queue.add(num);
            }
            else{
                if(queue.isEmpty()){
                    System.out.println("0");
                }
                else{
                    System.out.printf("%d\n",queue.poll());
                }
            }
        }
        
    }
}

1) 내장 자료구조 PriorityQueue 를 이용하자.

2) 절댓값이 작은 값이 나와야하니 이는 우선순위가 높게, 즉 절댓값이 작은 값이 앞쪽에 배치되어야 한다. 따라서 o1-o2의 리턴값이 양수여야한다.

3) queue는 기본적으로 add , peek , poll 이고 stack은 push, pop , peek 임을 잊지말자