[백준 알고리즘] 7662번: 이중 우선순위 큐 (JAVA)

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

---

소스코드

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

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

    for (int i=0; i<t; i++) {
        int k = Integer.parseInt(br.readLine());
        // 수가 들어갈 때마다 그 수의 개수를 세주면서, 키 값에 따라 오름차순으로 정렬하기 위해 TreeMap를 사용
        TreeMap<Integer, Integer> tm = new TreeMap<>(); 

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

          if (d == 'D') { // 수를 트리에서 빼는 경우
            if (tm.isEmpty()) continue;
            else {
              if (v == 1) {
                int tmp = tm.lastKey(); // tree의 최댓값
                int cnt = tm.get(tmp);
                if (cnt == 1) tm.remove(tmp); // 해당 수의 개수가 한개면, 트리에서 삭제
                else tm.put(tmp,cnt-1); // 한개 이상이면 갯수 1 감소 
                  
              } else {
                int tmp = tm.firstKey(); // 트리의 최솟값
                int cnt = tm.get(tmp);
                if (cnt == 1) tm.remove(tmp);
                else tm.put(tmp,cnt-1);
              }
            }
          } else{ // 수를 트리에 집어 넣는경우 
              tm.put(v,tm.getOrDefault(v,0)+1);
          }
	      }
      if (tm.isEmpty()) sb.append("EMPTY").append("\n");
      else sb.append(tm.lastKey()+" "+tm.firstKey()).append("\n");
	    }
    System.out.println(sb);
  }
}

 

---

풀이

★ 문제 제목도 이중 우선순위 큐여서 우선순위 큐를 활용해 푸는 방식을 고집했던 거 같습니다 ! 첨엔 두개의 우선순위 큐를 하나는 최대힙, 하나는 최소힙으로 만들어줬습니다. 그 후 입력 받는 값에 따라 각각의 큐에서 값을 제거해줬는데, 시간 제한이 6초임에도 불구하고 계속 시간초과 + 오답을 만날 수 있었습니다 ㅠㅠ 

 

★ 이건 뭔가 방식이 잘못되었다고 생각했고 구글링을 해보니,  java의 자료구조인 TreeMap을 활용해야 했습니다. java에 입문한지 얼마 안되어서 트리맵의 존재조차 몰랐는데, 풀면서 좋은 공부가 된 거 같습니다. 또한 우선순위 큐에서  remove() 하기 위해서는 큐를 탐색한 다음에 제거해줘야 하는데, 이는 O(n)의 시간이 걸리게 됩니다. 반면 TreeMap의 경우에는 O(logn)의 시간복잡도를 가지기에 더 효율적입니다 :) 

 

★ 자료구조를 알게 되니, 문제를 해결하는 아이디어는 비교적 쉽게 나온 거 같습니다. 트리맵은 맵의 구조를 가지고 있으며, 기본적으로 key값 기준으로 오름차순 정렬해줍니다. 이때 입력받는 값의 개수를 value로 세어주고, D가 입력으로 들어왔을 때, 최댓값 or 최솟값을 빼줘야 하는데 그 때마다 값을 빼주며,  value또한 1씩 감소시켜줬습니다 !

 

★ 모든 과정이 끝나고 트리맵이 비어있으면  empty를, 아니면 최댓값고 최솟값을 각각 StringBuilder에 입력해줬습니다 :)