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

 

 

 

하나는 최소 큐, 하나는 최대 큐로 정렬되어있는 우선순위 큐 두 가지를 선언해 풀었었는데, 시간 초과가 나왔다.

두 가지 큐를 사용하므로 최소 큐에서 값을 제거할 때 최대 큐에서도 같이 값을 제거해줘야 하는데 여기서 poll함수와 remove함수를 함께 쓰게 되서 시간복잡도가 O(N)이 나와 시간초과가 발생하게 된다.

 

poll함수에서는 문제가 없지만, remove함수를 사용할 때는 순차적으로 접근해서 발생하는 문제다.

 

 

문제를 해결하기 위해 TreeMap자료구조를 사용했다.

객체를 선언하면 자동으로 정렬이 되는 자료구조인데, TreeMap을 사용해 키 값을 기준으로 트리를 정렬시켜 저장하고 트리 형태로 빠르게 탐색을 진행할 수 있다.

 

 

Java

 

맞게 풀었는데 계속 틀렸다고 하길래.. 다시 보니 StringTokenizer를 잘못 사용하고 있었다.

 

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

public class Main {

  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringBuilder sb = new StringBuilder();
      
      int N = Integer.parseInt(br.readLine());

      for(int i=0; i<N; i++){
        int k = Integer.parseInt(br.readLine());
        TreeMap<Integer, Integer> tm = new TreeMap<>();

        for(int j=0; j<k; j++){
          StringTokenizer st = new StringTokenizer(br.readLine(), " ");
          char command = st.nextToken().charAt(0);
          int n = Integer.parseInt(st.nextToken());

          if(command == 'I'){
            int value = n;                      
            tm.put(value, tm.getOrDefault(value, 0)+1);          

          }else if(command == 'D'){

            if(tm.size()==0){
              continue;
            }
            
            if(n==1){
              
              int maxkey = tm.lastKey();
              if(tm.get(maxkey) == 1){
                tm.remove(maxkey);
              }else{
                tm.put(maxkey, tm.get(maxkey)-1);
              }

            }else if(n==-1){

              int minkey = tm.firstKey();
              if(tm.get(minkey)== 1){
                tm.remove(minkey);
              }else{
                tm.put(minkey, tm.get(minkey)-1);
              }
            }

            
          }
        }

        if(tm.size()==0){
          sb.append("EMPTY").append("\n");    
        }else{
          sb.append(tm.lastKey()).append(" ").append(tm.firstKey()).append('\n');
        }
   

          
     }

        System.out.println(sb);



      }
    }