[BOJ] 7662 이중 우선순위 큐 - JAVA

1. 문제

7662번: 이중 우선순위 큐

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

---

2. 풀이

TreeMap은 내부적으로 정렬이 되는 Map 구현체다. 여기서 TreeMap만 가지고 있는 firstKey(), lastKey()를 이용하려면 평소처럼 Map 타입에 TreeMap객체를 넣으면 안된다. TreeMap을 생성할 때 정렬순서를 지정할 수 있지만 key의 타입이 Integer라 굳이 지정하지 않았다.

 

입력이 "I"라면 map에 그대로 put한다. 단, 이미 있는 숫자라면 value값에 +1해서 넣는다.

입력이 "D"라면 다음의 절차를 따른다.

1. map 사이즈가 0이라면 아무것도 하지 않는다.

2. num이 양수라면 가장 큰 숫자를 삭제한다. map의 lastKey를 del에 저장한다. 

3. num이 음수라면 가장 작은 숫자를 삭제한다. map의 firstKey를 del에 저장한다.

4. map.get(del)이 몇 갠지 cnt에 저장한다. 만약 cnt=1이라면 map에서 del 을 아예 삭제한다.

5. cnt>1이라면 map.put(del,cnt-1)을 사용해서 갱신한다.

 

명령 입력이 모두 끝난 후 map의 사이즈가 0이라면 EMPTY를, 1이상이라면 map의 lastKey와 firstKey를 sb에 더한다.

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

public class BOJ_7662_이중우선순위큐 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      StringTokenizer st;

      for(int tc=0;tc<T;tc++){
         int K = Integer.parseInt(in.readLine());
         TreeMap<Integer, Integer> map = new TreeMap<>();
         for(int k=0;k<K;k++){
            st = new StringTokenizer(in.readLine());
            String command = st.nextToken();
            int num = Integer.parseInt(st.nextToken());
            switch (command){
               case "I":
                  map.put(num,map.getOrDefault(num,0)+1);
                  break;
               case "D":
                  if(map.size()==0) break;
                  int del = num>0? map.lastKey():map.firstKey();
                  int cnt = map.get(del);
                  if(cnt==1) map.remove(del);
                  else map.put(del,cnt-1);
                  break;
            }
         }

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

      System.out.print(sb);
   }
}

---

3. 결과

우선순위 큐 두 개를 사용해서 min, max를 구하고 map을 활용해서 유효한 숫자인지 검증하는 방법을 썼다. 다른 사람보다 시간이 너무 많이 걸려서 다른 방법을 찾다가 TreeMap의 firstKey, lastKey를 발견했다.

이 문제에서는 TreeMap을 쓰는게 더 올바른 방향 같다.