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

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

7662번: 이중 우선순위 큐

풀이

 

사용한 알고리즘 : 자료구조 중 Map(TreeMap)

 

풀이전략

해당 문제는 자료구조에 넣을 데이터들이 오름차순으로 정렬되어 저장되면서,

앞뒤로 삽입 및 삭제가 가능해야 한다.

 

데크를 사용하면 앞뒤로 삽입, 삭제가 가능하겠지만

오름차순으로 정렬시키기가 어렵다.

 

따라서 Map 중 TreeMap을 사용하여 자료구조 내 데이터를 오름차순으로 정렬하면서도키값을 통해 데이터에 접근해 앞뒤 또는 중간에 데이터를 삽입, 추가하거나 삭제하도록 한다.

 

정의할 Map에서 key값은 삽입할 값으로, value는 해당 값의 개수를 저장시키도록 정의한다.그러면 아래와 같은 입력을 주었을 경우

1
9
I -45
I 653
D 1
I -642
I 45
I 97
D 1
D -1
I 333

각 단계별로 아래와 같이 Map이 변경된다.

{-45=1}
{-45=1, 653=1}
{-45=1}
{-642=1, -45=1}
{-642=1, -45=1, 45=1}
{-642=1, -45=1, 45=1, 97=1}
{-642=1, -45=1, 45=1}
{-45=1, 45=1}
{-45=1, 45=1, 333=1}

 

연산 수행 중 map 내부가 비었을 경우 삭제 연산을 수행하지 않도록 qSize 변수를 사용했다.

 

제출코드

import java.io.*;
import java.util.StringTokenizer;
import java.util.TreeMap;

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

        int T = Integer.parseInt(br.readLine());

        for(int t=0;t<T;++t){
            TreeMap<Integer,Integer> map = new TreeMap<>();
            int qSize=0;
            int K = Integer.parseInt(br.readLine());
            for(int i=0;i<K;++i){
                st = new StringTokenizer(br.readLine());
                String command = st.nextToken();
                if(command.equals("I")){
                    int num = Integer.parseInt(st.nextToken());
                    map.put(num,map.getOrDefault(num,0)+1);
                    ++qSize;
                }
                else if(command.equals("D")){
                    int num = Integer.parseInt(st.nextToken());
                    if(num ==-1 && qSize>0){
                        int originNum = map.put(map.firstKey(),map.get(map.firstKey())-1);
                        if(originNum==1) map.remove(map.firstKey());
                        --qSize;
                    }
                    else if(num ==1 && qSize>0){
                        int originNum = map.put(map.lastKey(),map.get(map.lastKey())-1);
                        if(originNum==1) map.remove(map.lastKey());
                        --qSize;
                    }
                }
            }

            if(qSize==0){
                bw.write("EMPTY\n");
            }
            else{
                bw.write(map.lastKey()+" "+map.firstKey()+"\n");
            }
        }
        bw.flush();
        bw.close();
    }
}