[백준] 7662번 : 이중우선순위큐 - 자바(JAVA)

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

7662번: 이중 우선순위 큐

 

문제 해석

T : 테스트 케이스
Q : 적용할 연산의 개수(최대 백만개)
연산을 나타내는 문자 D 1 : 최대값을 삭제
연산을 나타내는 문자 D -1 : 최솟값을 삭제
연산을 나타내는 문자 I n : n을 삽입하는 연산
최종적으로 큐의 최댓값 최솟값을 출력, 비어있다면 EMPTY 출력

 

문제 풀이 전 설계

우선순위 큐를 2개 두어 해결하려고 하였습니다.

관건은 연산이 백만 번 일어나고 remove 연산은 O(n)이 발생합니다.

풀이

이중우선순위큐 + Map을 사용하여 해결하는 방법(remove 연산이 O(n)이기 때문에 줄이기 위해 Map사용)

TreeMap을 이용해서 해결하는 방법이 존재합니다.

TreeMap은 O(log N) 번에 연산을 수행하며 정렬이 되어있습니다. firstKey, lastKey를 통해 최대, 최솟값을 추출해낼 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main_7662_이중우선순위큐 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T; i++){

            TreeMap<Integer, Integer> doubleQ = new TreeMap<>();

            int K = Integer.parseInt(br.readLine());
            for(int j=0; j<K; j++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                char operation = st.nextToken().charAt(0);
                int num = Integer.parseInt(st.nextToken());
                if(operation == 'I'){
                    doubleQ.put(num, doubleQ.getOrDefault(num,0)+1);
                    continue;
                }
                //operation = 'D'
                if(doubleQ.isEmpty()){
                    continue;
                }
                //최댓값 추출
                int n = num == 1 ? doubleQ.lastKey() : doubleQ.firstKey();
                doubleQ.put(n,doubleQ.get(n)-1);
                if(doubleQ.get(n) == 0){

                    doubleQ.remove(n);
                }   
            }
            if(doubleQ.isEmpty()){
                sb.append("EMPTY\n");
                continue;
            }
            sb.append(doubleQ.lastKey() + " " + doubleQ.firstKey() + "\n");
        }
        System.out.println(sb.toString());

    }
}