백준 7662번 시간초과 (java)

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


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 = null;

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



        while(T-- >0){

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

            Map<Integer,Integer> map = new TreeMap<>();
            ArrayList<Integer> list = new ArrayList<>();
            while(k-- > 0){
              st=new StringTokenizer(br.readLine());
              char a = st.nextToken().charAt(0);
              int b = Integer.parseInt(st.nextToken());

              if(a=='I'){
                list.add(b);
                Collections.sort(list);
              }else if(a=='D' && list.size()>0) {
                  if(b==1){
                     list.remove(list.size()-1);
                  }else {
                      list.remove(0);
                  }
              }

            }
            if(list.size()==0) bw.write("EMPTY\n");
            else {
                int min = list.get(0);
                int max =list.get(list.size()-1);
                bw.write(Integer.toString(max)+" "+Integer.toString(min));
            }
        }
        bw.flush();
        bw.close();
        br.close();

    }

}

시간초과가 발생하는 이유

sort가 많은 시간을 잡아 먹는다.
그래서 sort정렬보다 counting 정렬을 사용하는게 더 시간이 절약됨을 보여주는 문제를 푼 적이 있다.

따라서 sort를 이용하지 않은 방법을 생각봐야한다.

그래서 생각해낸 접근법 시나리오는 아래와 같다.

1. PriorityQueue 내림차순, 하나는 오름차순으로 저장하는 2개의 우선순위 큐를 만든다.

2. 들어오는 값들을 HashMap에 저장한다. 중복된 값도 허용하기 때문에 같은 키가 들어 올때마다 값을 +1해준다.
   -> 값을 오름차순 우선순위 큐, 내림차순 우선순위 큐, Map 이 세곳에 모두 저장하는 것이다.

3. 최솟값, 최대값을 구하는 연산이 들어오면 Queue에서 꺼내주되 나갈 때는 -1해주고 결국 0이 될 때는 키를 삭제한다.

4. 단 조건이 있는데 map에는 삭제되었지만 Q에는 남아 있는 경우가 있을 수 있다.
   

위와 같은 경우를 생각하자
"D -1"이 들어오면 1이 Q에서 poll되지만 그 값을 map.get(1)를 했을 때 null이면 계속 남아있는 값을 뽑도록 poll을 해줘야 한다.

if(map.size()>0){
               int x =r_Q.poll();
               while(map.get(x)==null){
                   x=r_Q.poll();
               }
               map.put(x,map.get(x)-1);
               if(map.get(x)==0) map.remove(x);
           }

5. 마지막으로 여기서 주의해야할 부분이 있다.

   Q = new PriorityQueue<> ();
   // r_Q = new PriorityQueue<>((x1,x2)->x2-x1); // 오버플로우, 언더플로우 발생
   r_Q = new PriorityQueue<>((x1,x2)-> x2 >= x1? 1: -1);

   이 부분을 고려하지 않으면 96%에서 틀렸습니다가 뜬다. 그래서 최종적으로의 풀이는 아래와 같다.
   

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

public class Main{


   static PriorityQueue<Integer> Q ;
   static PriorityQueue<Integer> r_Q ;
   static Map<Integer,Integer> map ;

   public static void main(String[] args) throws IOException{

       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));

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




       while( T-- >0) {
           Q = new PriorityQueue<> ();
          // r_Q = new PriorityQueue<>((x1,x2)->x2-x1); // 오버플로우 발생여부 있음
           r_Q = new PriorityQueue<>((x1,x2)-> x2 >= x1? 1: -1);
           map = new HashMap<>();
           int k = Integer.parseInt(br.readLine());
           for(int i=0;i<k;i++){
               StringTokenizer st = new StringTokenizer(br.readLine()," ");
               char m = st.nextToken().charAt(0);
               int y = Integer.parseInt(st.nextToken());
               if(m=='D'){
                   delete(y);
               }else{
                   Q.offer(y);
                   r_Q.offer(y);
                   map.put(y,map.getOrDefault(y,0)+1);
               }

           }

          if(map.size()==0) bw.write("EMPTY\n");
          else{
              Set<Integer> set = map.keySet();
              Iterator it =set.iterator();
              Integer min = Integer.MAX_VALUE;
              Integer max = Integer.MIN_VALUE;
              while(it.hasNext()){
                  Integer x = (Integer)it.next();
                  if(min>x) min=x;
                  if(max<x) max=x;
              }
              bw.write(Integer.toString(max)+" "+Integer.toString(min)+"\n");
          }

       }//while(T)
       bw.flush();
       bw.close();
       br.close();

   }

   static void delete(int y){
       if(y==-1){//최솟값 삭제
            if(map.size()>0){
                int x =Q.poll();
                while(map.get(x)==null){
                    x=Q.poll();
                }
                map.put(x,map.get(x)-1);
                if(map.get(x)==0) map.remove(x);
            }
       }else{
           if(map.size()>0){
               int x =r_Q.poll();
               while(map.get(x)==null){
                   x=r_Q.poll();
               }
               map.put(x,map.get(x)-1);
               if(map.get(x)==0) map.remove(x);
           }

       }

   }





}