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

문제

- 이중 우선순위 큐는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있음

- 차이점은 데이터를 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 것

- 각 줄에 연산을 나타내는 문자('D' 또는 'I')와 정수 n이 주어짐

- 'I n'은 정수 n을 큐에 삽입하는 연산 (동일한 정수가 삽입될 수 있음)

- 'D 1'는 큐에서 최댓값 삭제 / 'D -1'는 큐에서 최솟값 삭제 (최댓값, 최솟값이 둘 이상인 경우 하나만 삭제 됨)

- 큐가 비어있는데 적용할 연산이 'D'라면 무시 가능

- 모든 연산을 처리하고 최종적으로 큐에 저장된 데이터 중 최댓값과 최솟값 출력

 

해결방법

TreeMap 자료 구조를 활용하여 문제를 해결하였다. 숫자와 해당 숫자가 들어있는 개수를 함께 treemap에 저장할 수 있도록 구성하였다. 삽입 과정에서 getOrDefault 메서드를 사용하여 각 숫자가 몇개가 포함되어 있는지 확인할 수 있도록 하였다. getOrDefault 메서드에 대한 자세한 사용법은 아래 포스팅을 확인하면 좋을 것 같다. 

[자료구조] TreeMap - getOrDefault

삭제 과정에서는 연산 내용(1, -1)에 따라 treemap에 저장된 숫자들 중에서 최댓값, 최솟값을 구해서 개수를 줄여주거나 개수가 1개인 경우엔 삭제할 수 있도록 하였다.

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int tc = 1; tc<=T; tc++) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> treemap = new TreeMap<>();

            for(int i = 0; i<k; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                // 삽입 연산
                if(st.nextToken().equals("I")) {
                    int num = Integer.parseInt(st.nextToken());
                    // 해당 숫자가 있는지 확인하여 개수와 함께 저장
                    treemap.put(num, treemap.getOrDefault(num, 0) + 1);
                } 
                // 삭제 연산
                else {
                    int num = Integer.parseInt(st.nextToken());
                    // 최댓값 삭제
                    if(num == 1) {
                        if(treemap.size() == 0) continue;
                        // 최댓값 개수 받아오기
                        int value = treemap.get(treemap.lastKey());
                        // 개수가 1개라면 아예 treemap에서 삭제
                        if(value == 1) treemap.remove(treemap.lastKey());
                        // 1개 이상이라면 개수 -1
                        else treemap.put(treemap.lastKey(), value-1);
                    } 
                    // 최솟값 삭제
                    else {
                        if(treemap.size() == 0) continue;
                        // 최솟값 개수 받아오기
                        int value = treemap.get(treemap.firstKey());
                        // 개수가 1개라면 아예 treemap에서 삭제
                        if(value == 1) treemap.remove(treemap.firstKey());
                        // 1개 이상이라면 개수 -1
                        else treemap.put(treemap.firstKey(), value-1);
                    }
                }
            }
            // treemap이 비었다면 EMPTY 출력
            if(treemap.size() == 0) System.out.println("EMPTY");
            // 최댓값 최솟값 출력
            else System.out.println(treemap.lastKey() + " " + treemap.firstKey());
        }
    }
}