[BOJ/JAVA] 7662번: 이중 우선순위 큐

7662번: 이중 우선순위 큐

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

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

키워드

• 데이터를 삽입하는 연산

• 데이터를 삭제하는 연산은 또 두 가지로 구분
  • 우선순위가 가장 높은 것을 삭제
  • 우선순위가 가장 낮은 것을 삭제

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

---

구현

TreeMap을 이용하여 이중 우선순위 큐를 구현했다.

TreeMap<Integer,Integer> 형식으로 선언했으며, <데이터, 데이터의 갯수> 형식의 데이터를 저장한다.

삽입연산

• I 값이 들어오면 getOrDefault를 이용하여 없으면 1, 있으면 해당 값에 +1을 해준다.

삭제연산

• 1 :: 최댓값을 삭제하는 연산
  • treeMap.lastKey를 이용하여 가장 큰 값을 가져온다.
  • 데이터 갯수를 -1을 해주고, 만약 0이 된다면 remove메소드를 호출한다.

• -1 :: 최솞값을 삭제하는 연산
  • treeMap.lastKey를 이용하여 가장 작은 값을 가져온다.
  • 데이터 갯수를 -1을 해주고, 만약 0이 된다면 remove메소드를 호출한다.

---

코드

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

public class java_7662 {
    static int T;
    static int k;

    // Key에 따라 정렬
    // 1 삽입, (1,1), 1 삽입(2), (1,2)
    // 삭제 -> (1,1)
    // Dict -> 삭제 O(1)
    // 삽입 -> O(lgN)
    static TreeMap<Integer, Integer> treeMap;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int testCase = 0; testCase < T; testCase++) {
            treeMap = new TreeMap<>();

            k = Integer.parseInt(br.readLine());

            for (int i = 0; i < k; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                char command = st.nextToken().charAt(0);
                int number = Integer.parseInt(st.nextToken());

                if (command == 'I') {
                    treeMap.put(number, treeMap.getOrDefault(number, 0) + 1);
                    continue;
                }

                if (command == 'D') {
                    if (treeMap.isEmpty()) {
                        continue;
                    }
                    if (number == 1) {
                        int maxValue = treeMap.lastKey();
                        treeMap.put(maxValue, treeMap.get(maxValue) - 1);

                        if (treeMap.get(maxValue) == 0) {
                            treeMap.remove(maxValue);
                        }
                        continue;
                    }

                    if (number == -1) {
                        int minValue = treeMap.firstKey();
                        treeMap.put(minValue, treeMap.get(minValue) - 1);

                        if (treeMap.get(minValue) == 0) {
                            treeMap.remove(minValue);
                        }
                        continue;
                    }
                }
            }

            if (treeMap.isEmpty()) {
                System.out.println("EMPTY");
            } else {

                System.out.printf("%d %d\n", treeMap.lastKey(), treeMap.firstKey());
            }
        }

        br.close();

    }
}

---

Uploaded by N2T