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

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

7662번: 이중 우선순위 큐

예전에 프로그래머스에서 똑같은 문제를 풀이했던 적이 있다.

이번에는 우선순위 큐를 사용하는 것이 아닌 다른 방법을 사용하였다.

 

핵심

https://kimtaesoo99.tistory.com/135

[프로그래머스] 이중우선순위큐

기존에 풀이는 작은 값 우선순위 큐와 큰 값 우선순위 큐 2개를 생성하여, 한쪽에서 삭제하면 다른 쪽에서도 삭제를 해줘야 했다.

이러한 방식은 시간복잡도 측에서 매우 불리하다. 따라서 이번에는 TreeMap을 사용하여 풀이하였다.

 

 

정답 코드

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

public class Main {
    public static void main(String[] args)throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int test_case = Integer.parseInt(br.readLine());
        for (int i = 0; i < test_case; i++){
            int calculate = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> q = new TreeMap<>();
            for (int j = 0; j < calculate; j++){
                String[] option = br.readLine().split(" ");
                String c = option[0];
                int value = Integer.parseInt(option[1]);
                if (c.equals("I")){
                    q.put(value, q.getOrDefault(value, 0) + 1);
                }else {
                    if (q.isEmpty())continue;

                    int delete = value == 1 ? q.lastKey() : q.firstKey();

                    if (q.put(delete, q.get(delete)-1) == 1) {
                        q.remove(delete);
                    }
                }
            }
            if (q.isEmpty()) sb.append("EMPTY").append("\n");
            else sb.append(q.lastKey()).append(" ").append(q.firstKey()).append("\n");
        }
        System.out.println(sb);
    }
}

해설

이 문제의 핵심은 TreeMap을 사용하는 것이다. 

TreeMap의 경우 이진트리를 기반으로 오름차순으로 정렬된 형태이다. 따라서 firstKry()와 lastKey()를 사용하여 

간단하게 풀 수 있다.

 

if (q.put(delete, q.get(delete)-1) == 1)

이 조건문의 경우에는 q.put(~)을 할 경우 put을 한 상태가 아닌, 이전의 값을 보여주기 때문에 만약 이전에 1이었다면,

값을 삭제한다. 이후에 값이 -1이 적용된다.

 

 

배운 점

TreeMap을 사용할 생각을 못했었다.

당연하게 우선순위 큐를 사용하여 풀려했는데, TreeMap을 사용하니, 코드가 더 짧아지고, 쉽게 풀렸다.

여러 가지 풀이법을 배우고 적용해 보는 것이 학습이나 논리적 사고에 도움이 많이 되는 것 같다.