이중 우선순위 큐(7662)

이중 우선순위 큐(7662)

import java.io.*;
import java.util.*;
import java.util.Map.Entry;

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));
    StringBuilder sb = new StringBuilder();
  
    StringTokenizer st;
    
    // 테스트 횟수
    int t = Integer.parseInt(br.readLine());
    
    // 이중 우선순위 큐의 역할
    // TreeMap은 tree 구조로 값 입력 시 key를 기준으로 오름차순 정렬된다
    TreeMap<Integer, Integer> tm;
    
    while(t-- > 0) {
      
      // 객체 생성
      tm = new TreeMap<Integer, Integer>();
    
      // 연산 갯수
      int k = Integer.parseInt(br.readLine());
      
      while(k-- > 0) {
        st =  new StringTokenizer(br.readLine());
        // I or D
        char ch =   st.nextToken().charAt(0);
        // 입력값
        int n = Integer.parseInt(st.nextToken());
        
        // I 이면
        if(ch == 'I') {
          // map의 형태라서 key가 중복이 안되므로, value에다가 입력된 n의 개수 카운팅
          // 이미 들어가 있는 값이면 value + 1, 아니면 value = 1로 생성
          if(tm.containsKey(n)) tm.put(n, tm.get(n)+1);
          else tm.put(n, 1);
        } else {
          
          // map이 비어있지 않다면, D 연산 수행
          if(!tm.isEmpty()) {
            if(n == 1) {
              
              // 오름차순 정렬이므로 마지막 요소는 최대값
              Entry<Integer, Integer> ent = tm.lastEntry();

              // value가 1이면 tm에서 삭제, 아니면 -1 카운트
              if(ent.getValue() == 1) tm.remove(ent.getKey());
              else tm.put(ent.getKey(), ent.getValue() - 1);
            } else {
              // 처음 요소는 최소값
              Entry<Integer, Integer> ent = tm.firstEntry();
              if(ent.getValue() == 1) tm.remove(ent.getKey());
              else tm.put(ent.getKey(), ent.getValue() - 1);
            }
          }
        }
      }
      
      if(tm.isEmpty()) sb.append("EMPTY").append("\n");
      else {
        Entry<Integer, Integer> ent = tm.lastEntry();
        sb.append(ent.getKey()).append(" ");
        ent = tm.firstEntry();
        sb.append(ent.getKey()).append("\n");
      }
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

1. 처음에는 Deque와 Comparator를 사용하여 Deque에 오름차순으로 정렬을 하는 방향으로 생각했다.
2. 하지만 구현하기가 어려웠으며, 감이 잡히지 않았다.
3. 다른 사람들의 풀이를 참고해보니, TreeMap을 알게되었다.
4. 물론 TreeMap에 대한 개념은 알고 있었지만, 사용해본 적이 없었기에 TreeMap을 이용하여 풀어야겠다는 생각을 못했었다.
5. TreeMap을 이용하였고, 나머지는 요청에 따라 코드를 구현하였다.

- 성공
- 메모리 : 359648 KB
- 시간 : 2648 ms

보안점

1. TreeMap에 대해 알게 되었고, 아직도 배울게 참 많다는 것을 느꼈다..