[백준 7662] 이중 우선순위 큐 (JAVA)

백준 7662번 문제 - 이중 우선순위 큐

7662번: 이중 우선순위 큐

---

문제 분석

 

 

• 이중 우선순위 큐가 있다고 가정하고 문제를 푼다.
• 입력 받을 테스트 개수를 입력받고, 각 케스트에서 연산 수를 입력 받는다. 그리고 연산을 실행하고 가장 큰 값, 가장 작은 값을 출력한다. (이중 우선순위 큐의 첫번째와 마지막 값을 출력) 만약 값이 없으면 EMPTY를 출력하라.
  • 연산 풀이
    1) D num : [ num == 1 ] 최댓값 삭제 | [ num == -1 ] 최솟값 삭제 
    2) I  num : num을 큐에 추가한다.

---

해결 키 포인트

 

• 시간이 많지 않다. (WHY? 테스트 케이스 값 T가 크지 않아서)
  • TreeMap을 사용해서 자동 정렬 및 값에 따른 개수 등록

 

고민됐던 부분

우선순위 큐 : 우선순위 큐 두개를 사용하기 보다 큐 하나를 두고, 최댓값을 출력해야 할 때만 큐에 있는 모든 걸 꺼내 출력하는 식으로 해서 시간초과
Deque : 앞에서 뒤에서 빼는 건 쉬우나, 정렬할 때 시간이 오래 걸려 시간초과
ArrayList : 미친 척하고 ArrayList 제작 후 값을 입력받을 때마다 Collections.sort 함수 이용, 이 역시 시간 초과
TreeSet과 HashMap : 인터넷 찾아보니 자동으로 정렬해주고 앞 뒤에서 꺼낼 수 있는 TreeSet이 존재하길래 사용하였으나, TreeSet은 중복 값 사용이 안되서 HashMap 사용 (좀 더 쉬운 방법 모색)
TreeMap : 위에 TreeSet과 HashMap을 하나로 만든 클래스로, 이를 사용해서 문제 풀이

 

---

코드

 

import com.sun.source.tree.Tree;

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));

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

        for (int t = 0; t < T; t++) {
            // 가장 큰 수, 가장 작은 수를 알아내기 쉽게 treemap 사용 (value는 그 값의 개수)
            TreeMap<Integer, Integer> treeMet = new TreeMap<>();

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

            for (int k = 0; k < K; k++) {
                StringTokenizer st = new StringTokenizer(br.readLine());

                String mode = st.nextToken();
                int num = Integer.parseInt(st.nextToken());

                // mode가 I일때, tree map에 삽입
                if (mode.equals("I")) {
                    if(treeMet.containsKey(num)) {
                        treeMet.put(num, treeMet.get(num)+1);
                    }
                    else {
                        treeMet.put(num, 1);
                    }
                }

                // mode가 D일 경우, tree map에서 최댓값 및 최솟값 1개만 삭제
                else {
                    // tree map이 비어있지 않을 경우만
                    if (!treeMet.isEmpty()) {
                        // 최댓값 삭제
                        if (num == 1) {
                            int last = treeMet.lastKey();
                            if(treeMet.get(last) == 1) {
                                treeMet.remove(last);
                            }
                            else {
                                treeMet.put(last, treeMet.get(last)-1);
                            }
                        }
                        // 최솟값 삭제
                        else {
                            int first = treeMet.firstKey();
                            if(treeMet.get(first) == 1) {
                                treeMet.remove(first);
                            }
                            else {
                                treeMet.put(first, treeMet.get(first)-1);
                            }
                        }
                    }
                }
            }

            // 비어있을 경우 출력
            if (treeMet.isEmpty()) {
                bw.write("EMPTY\n");
            }
            // 남이 있을 경우 출력
            else {
                bw.write(treeMet.lastKey() + " " + treeMet.firstKey()+"\n");
            }
        }
        bw.flush();
        bw.close();
    }
}