백준 7662번: 이중 우선순위 큐

 

문제를 보자마자 처음에는 우선순위 큐를 이용해야겠다고 생각했다.

1. 우선순위큐 선언
2. I 연산시 단순 우선순위큐 삽입
3. D연산시 -1이면 현재 큐의 우선순위를 뒤집어서 사용

하지만 위 방법을 사용시 3번이 문제가 된다.
자바에서는... 이미 사용하고있는 우선순위 큐의 우선순위 정의를 다르게 하는 메소드도 없을 뿐더러,
직접 정의한다면 새로운 우선순위큐를 만들어서 옮겨 넣는 방법 뿐이다.
D 연산 때 마다 이렇게하면 Timeout이 발생할 것이다.

---

그래서 다음 방법으로는 Deque를 이용해야겠다고 생각했다.

1. Deque선언
2. D연산시, 1이면 앞에서부터 제거, -1이면 뒤에서부터 제거
3. I연산시 단순 삽입 후, 크기순으로 정렬

하지만 위 방법 역시 3번이 문제가 된다.
Deque역시 정렬하는 방법이 까다롭다. List로 변환 후 정렬, 그리고 다시 Deque로 바꿔야한다.
I연산마다 이렇게 하면 역시 Timeout이 발생할 것 같다.

---

그리고 생각해낸 방법이 우선순위 큐를 두 개 사용하는 방법이다.

1. 큰 값이 우선순위인 큐, 작은 값이 우선순위인 큐를 각각 선언한다.
2. I 연산에서는 두 큐에 모두 삽입한다.
3. D연산에서 1일 때는 maxQueue에서 삭제
   -1일 때는 minQueue에서 삭제
4. 출력할 때, max값은 maxQueue에서 peek()값
   min 값은 minQueue에서 peek()값
5. 단, max <= min 이면 EMPTY를 출력

그 코드는 아래와 같다.

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

		PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>(); // 최소값 우선순위 큐
		PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>(Collections.reverseOrder()); // 최대값 우선순위 큐

		int t = Integer.parseInt(br.readLine()); // 테스트케이스 개수
		for (int i = 0; i < t; i++) {
			int k = Integer.parseInt(br.readLine()); // 연산의 개수
			for (int j = 0; j < k; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String command = st.nextToken();
				int num = Integer.parseInt(st.nextToken());
				switch (command) {
				case "I": // 삽입 연산
					minQueue.add(num);
					maxQueue.add(num);
					break;
				case "D": // 삭제 연산
					if (num == 1 && !maxQueue.isEmpty()) {
						maxQueue.poll();
					} else if (num == -1 && !minQueue.isEmpty()) {
						minQueue.poll();
					}

				}
			}
			int max = maxQueue.peek(); // 최대값은 최대값 우선순위 큐에서 탐색
			int min = minQueue.peek(); // 최소값은 최소값 우선순위 큐에서 탐색
			if (max <= min) { // 한 개의 큐를 두개로 나눴기 때문에, 만약 최소값 최대값이 같거나 작으면, 한 개의 큐로 봤을 때는 큐가 빈 것과 같음
				bw.write("EMPTY\n");
			} else {
				bw.write(max + " " + min + "\n");
			}
		}

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

}

위 코드는 잘 동작하지만, 아래 테스트 케이스에서 오답을 낸다.

1
9
I 1
I 2
I 3
D 1
D -1
I 4
I 5
D 1
D -1

위 테스트 케이스는 4 4를 출력해야하지만 내 코드는 4 3을 출력한다.
그리고 EMPTY의 조건으로 정의했던 (max <= min 이면 EMPTY를 출력)도 맞지 않는 조건인 것 같다.

EMPTY를 정의할 수 있는 다른 방법이 필요하다.

---

문제는
D 1 연산일 때는 maxQueue에서 삭제, D -1 연산일 때는 minQueue에서 삭제
하다보니 삭제되어야하지만 둘 중 하나의 큐에 원소가 남아있는 경우가 있는 것이다.

이를 해결하기 위해 HashMap을 사용하여, 큐에 숫자가 몇개 들어있는지 cnt할 수 있도록 한다.
HashMap은 num을 Key로, num의 개수를 value로 하는 { num : cnt } 구조를 갖는다.

I연산일 때는 cnt를 1씩 증가, D연산일 때는 cnt를 감소시킨다.
즉, cnt가 2인 num은 큐에 num이 2개 있다는 뜻이고, cnt가 0인 num은 queue에서 모두 제거된 원소인 것이다.

주의할 점으로는, cnt가 0인데 Queue에 값이 있는 경우이다. 이 경우에는 Queue에 들어있는 해당 num을 모두 제거한다.
이렇게 제거되지 않고 큐에 남아있는 원소를 제거할 수 있는 장치를 마련했다.

마지막으로 출력하기 전에 map을 한번 더 검사하여 cnt가 0인 원소를 queue에서 제거한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

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 i = 0; i < t; i++) {
			int k = Integer.parseInt(br.readLine());

			PriorityQueue<Integer> maxQueue = new PriorityQueue<>(Collections.reverseOrder());
			PriorityQueue<Integer> minQueue = new PriorityQueue<>();
			HashMap<Integer, Integer> map = new HashMap<>(); // 삭제된 원소를 추적하기 위한 HashMap

			for (int j = 0; j < k; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String command = st.nextToken();
				int num = Integer.parseInt(st.nextToken());
				System.out.println(j + ")" + command + " " + num);

				// n을 두 큐에 추가
				if (command.equals("I")) {
					maxQueue.add(num);
					minQueue.add(num);
					// 입력 num의 cnt횟수 저장
					map.put(num, map.getOrDefault(num, 0) + 1);
				} else if (command.equals("D")) {
					// 최대값 삭제 연산
					if (num == 1) {
						// 실제로는 지워진 원소인데 큐에 남아있는경우
						while (!maxQueue.isEmpty() && map.get(maxQueue.peek()) == 0) {
							maxQueue.poll(); // 해당 원소를 큐에서 모두 제거
						}
						// 보통의 경우
						if (!maxQueue.isEmpty()) {
							int max = maxQueue.poll(); // 큐에서 원소 제거
							map.put(max, map.get(max) - 1); // map에서 해당 num의 cnt -1
						}
					} else if (num == -1) { // 최소값 삭제 연산
						while (!minQueue.isEmpty() && map.get(minQueue.peek()) == 0) {
							minQueue.poll();
						}
						if (!minQueue.isEmpty()) {
							int min = minQueue.poll();
							map.put(min, map.get(min) - 1);
						}
					}
				}
			}
			// 큐에서 제거된 원소들을 실제로 큐에서 제거
			while (!maxQueue.isEmpty() && map.get(maxQueue.peek()) == 0) {
				maxQueue.poll();
			}
			while (!minQueue.isEmpty() && map.get(minQueue.peek()) == 0) {
				minQueue.poll();
			}

			if (maxQueue.isEmpty() || minQueue.isEmpty()) {
				bw.write("EMPTY\n");
			} else {
				bw.write(maxQueue.peek() + " " + minQueue.peek() + "\n");
			}
		}

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