백준 7662 이중 우선순위 큐 with 자바

---

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

풀이

문제 제목이 우선순위 큐라고 해서 진짜 우선순위 큐로 풀면 안 된다

이 문제는 기본적인 자료구조를 잘 알고 있는지 묻는 문제이다

특히 Tree에 관한 자료구조를 잘 알고 있어야 한다

 

필자는 TreeMap을 이용하여 문제를 풀었다

똑같은 숫자를 여러 개 저장하는 경우도 있으므로

숫자의 카운트를 위해 TreeSet보다는 TreeMap을 사용하였다

물론 TreeSet을 사용하는 경우, 해당 숫자의 개수를 별도로 카운트해주면 문제를 풀 수 있긴 할 것이다

하지만 숫자의 범위가 너무 넓으므로, 각 숫자의 개수를 따로 카운트해주는 것은 별로인 듯하다

 

입력 받는 숫자의 범위가 32비트 정수이므로

숫자를 저장할 key는 long형으로,

해당 숫자의 카운트를 세어줄 value는 int형으로 Map을 생성한다

TreeMap<Long, Integer> map = new TreeMap();

 

입력받은 명령이 "I"인 경우

map에 입력받은 숫자를 저장한다

이미 해당 숫자가 저장되어 있을 경우 value값을 증가시킨다

if (map.containsKey(n)) map.put(n, map.get(n) + 1);
else map.put(n, 1);

 

입력받은 명령이 "D 1"인 경우

최댓값이 가지고 있는 value를 1 줄여준다

만약, value가 1인 경우 map에서 해당 key를 삭제해준다

if (!map.isEmpty()) {
    Map.Entry e = map.lastEntry();
    if ((int) e.getValue() == 1) map.remove(e.getKey());
    else map.put((long) e.getKey(), (int) e.getValue() - 1);
}

 

입력받은 명령이 "D -1"인 경우

최솟값이 가지고 있는 value를 1 줄여준다

만약, value가 1인 경우 map에서 해당 key를 삭제해준다

if (!map.isEmpty()) {
    Map.Entry e = map.firstEntry();
    if ((int) e.getValue() == 1) map.remove(e.getKey());
    else map.put((long) e.getKey(), (int) e.getValue() - 1);
}

 

---

 

전체 코드

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

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

                String command = st.nextToken();
                long n = Long.parseLong(st.nextToken());

                if (command.equals("I")) {
                    if (map.containsKey(n)) map.put(n, map.get(n) + 1);
                    else map.put(n, 1);
                } else {
                    if (n == 1) {
                        if (!map.isEmpty()) {
                            Map.Entry e = map.lastEntry();
                            if ((int) e.getValue() == 1) map.remove(e.getKey());
                            else map.put((long) e.getKey(), (int) e.getValue() - 1);
                        }
                    } else {
                        if (!map.isEmpty()) {
                            Map.Entry e = map.firstEntry();
                            if ((int) e.getValue() == 1) map.remove(e.getKey());
                            else map.put((long) e.getKey(), (int) e.getValue() - 1);
                        }
                    }
                }
            }

            if (!map.isEmpty()) {
                Map.Entry last = map.lastEntry();
                Map.Entry first = map.firstEntry();
                bw.write(last.getKey() + " " + first.getKey() + "\n");
            } else {
                bw.write("EMPTY\n");
            }
        }

        bw.flush();
        bw.close();
    }
}