[백준] 7662번: 이중 우선순위 큐 - JAVA

🔗 문제 링크

BOJ 7662번: 이중 우선순위 큐

7662번: 이중 우선순위 큐

 

1️⃣ PriotyQueue

📝 풀이 과정

큰 값과 작은 값으로 정렬해야 하기 때문에 고민하다 PriorityQueue를 두 개 사용하여 작은 값을 기준으로하는 minQueue와 큰 값을 기준으로 하는 maxQueue를 선언하였다.

기본적으로 PriorityQueue는 작은 값이 먼저 poll되기 때문에 maxQueue에는 Collections.reverseOrder()를 활용해 반대로 정렬하였다.

 

하지만, 문제는 minQueue에서 poll을 하여도 maxQueue에서는 제거가 되지 않는다는 점이다. 단순히 remove를 사용한다면 remove함수를 살펴보면 알겠지만 순차적으로 접근하여 equals == true일 경우 제거하기 때문에 O(N) 이기 때문에 시간초과가 발생하게 된다.

 

따라서, Map을 통해 숫자와 해당 숫자의 갯수를 저장하기로 했다.
Insert할 때, map.getOrDefefault를 통해 없다면 0을 반환시켜 +1한 값을 put해주었다.
Delete는 queue에서 poll하며 값을 꺼내고 해당 값이 map에 해당 값이 존재하지 않는다면 반복해서 poll을 진행한다. 만약 존재한다면 map의 value를 하나 감소시킨 값을 다시 put하고 만약 1이라면 map에서 삭제하였다.

 

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            int k = Integer.parseInt(br.readLine());
            Map<Integer, Integer> map = new HashMap<>();
            PriorityQueue<Integer> minQue = new PriorityQueue<>();
            PriorityQueue<Integer> maxQue = new PriorityQueue<>(Collections.reverseOrder());

            for (int i = 0; i < k; i++) {
                String[] input = br.readLine().split(" ");
                char ch = input[0].charAt(0);
                int n = Integer.parseInt(input[1]);

                if (ch == 'I') {
                    map.put(n, map.getOrDefault(n, 0) + 1);

                    minQue.add(n);
                    maxQue.add(n);
                } else {
                    if (map.size() == 0)
                        continue;

                    PriorityQueue<Integer> que = n == 1 ? maxQue : minQue;
                    removeMap(que, map);
                }
            }

            if (map.size() == 0)
                System.out.println("EMPTY");
            else {
                int n = removeMap(maxQue, map);
                System.out.println(n + " " + (map.size() > 0 ? removeMap(minQue, map) : n));
            }

        }

    }

    static int removeMap(PriorityQueue<Integer> que, Map<Integer, Integer> map) {
        int num;
        while (true) {
            num = que.poll();
            int cnt = map.getOrDefault(num, 0);

            if (cnt == 0)
                continue;

            if (cnt == 1)
                map.remove(num);
            else
                map.put(num, cnt - 1);

            break;
        }

        return num;
    }

}

 

📊 제출 결과

 

---

2️⃣ TreeMap

📝 풀이 과정

문제를 푼 뒤 다른 사람들이 한 코드를 보기 시작했고, TreeMap을 사용하여 더 쉽고 간단한 코드의 구성이 가능했다.
정렬이 가능한 Map이라 알고는 있었지만 항상 선언할 때 마다 Map map = new TreeMap()형태로 사용했기 때문에 Map 인터페이스에 존재하는 함수만 사용해 TreeMap의 내부 함수를 잘 몰랐던게 컸던 것 같다.

 

TreeMap은 이진 트리를 기반으로 오름차순으로 정렬된 형태로 저장한다. 따라서 firstKey()와 lastKey()는 O(logN) 만큼 밖에 소요되지 않는다!

map에는 위의 경우와 마찬가지로 숫자와 해당 숫자가 저장된 갯수를 저장하였고, delete시 마다 - 1한 값을 다시 put해주었다.

 

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> que = new TreeMap<>();

            for (int i = 0; i < k; i++) {
                String[] input = br.readLine().split(" ");
                char ch = input[0].charAt(0);
                int n = Integer.parseInt(input[1]);

                if (ch == 'I') {
                    que.put(n, que.getOrDefault(n, 0) + 1);
                } else {
                    if (que.size() == 0)
                        continue;

                    int num = n == 1 ? que.lastKey() : que.firstKey();
                    if (que.put(num, que.get(num) - 1) == 1)
                        que.remove(num);
                }
            }

            System.out.println(que.size() == 0 ? "EMPTY" : que.lastKey() + " " + que.firstKey());
        }

    }

}

 

📊 제출 결과