📝 문제

첫번째 시도

Priority Queue 하나를 사용해서 수를 정렬하고, 끝 지점(현재의 최소값)을 표시할 포인터를 둔다.
"I n"이 입력되었을 때 큐에 추가하고 포인터를 한 칸 오른쪽으로 옮긴다(+1 한다)
"D 1"이 입력되었을 때 poll() 연산을, "D -1"이 입력되었을 때 포인터를 한 칸 왼쪽으로 옮긴다 (-1 한다)
이렇게 했을 때, 삭제했다가 새로운 수를 삽입할 때 포인터 이동 처리를 할 수가 없다. 그래서 이 방법은 적절하지 않다

두번째 시도

문제 그대로 이중 우선순위 큐니까 우선순위 큐 두 개를 초기화해서 하나는 오름차순으로 정렬, 다른 하나는 내림차순으로 정렬할까... 하다가! 설마 그 방법은 아니겠지라는 생각이 들어 다른 자료구조를 사용하여 구현해봐야겠다는 생각이 들었다.
그래서 선택한 것이 TreeMap이다.
TreeMap은 red-black tree의 방법으로 삽입 시에 바로 정렬이 되는 자료구조이다. 그래서 삽입 시에 O(log N)의 시간복잡도가 소요된다. 또한 lastKey()와 firstKey()를 통해 값을 가져오는 연산도 O(log N)이라는 시간복잡도 밖에 소요되지 않는다. 따라서 I와 함께 입력되는 정수를 키 값으로 저장하고, 해당 수가 몇 개 입력되어 있는지를 value로 하여 TreeMap에 삽입하고, 삭제할 때는 해당 수를 찾아 map에서 삭제하고 value를 1 줄여 다시 삽입한다.

📌 코드

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class boj7662 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    StringTokenizer st;
    // initialize treemap<value, count>
    TreeMap<Integer, Integer> tm = new TreeMap<>(); // 작은 값이 앞에, 큰 값에 뒤에 저장됨
    // test-case
    int t = Integer.parseInt(br.readLine());
    for(int i = 0; i < t; i++){
      int k = Integer.parseInt(br.readLine());
      tm.clear();
      for(int j = 0; j < k; j++){
        st = new StringTokenizer(br.readLine());
        char func = st.nextToken().charAt(0);
        int num = Integer.parseInt(st.nextToken());
        // function
        // insert
        if(func == 'I'){
          // 같은 값이 삽입될 경우, count+1
          tm.put(num, tm.getOrDefault(num, 0)+1);
        }
        // delete
        else{
          // pass if map size == 0
          if(tm.isEmpty()) continue;
          int value, cnt;
          // delete max
          if(num == 1){
            value = tm.lastKey();
          }
          //delete min
          else{
            value = tm.firstKey();
          }
          cnt = tm.get(value);
          // delete if count == 1
          tm.remove(value);
          if(cnt > 1) tm.put(value, cnt-1);
        }
      }
      // print empty
      if(tm.isEmpty()) sb.append("EMPTY\n");
      // print max, min
      else{
        sb.append(tm.lastKey()).append(" ").append(tm.firstKey()).append("\n");
      }
    }
    System.out.println(sb.toString());
  }
}