백준 7662 JAVA - 이중 우선순위 큐

1. I value -> value 넣기
2. D -1 -> 최솟값 빼기
3. D 1 -> 최댓값 빼기
4. k <= 1,000,000, 값들은 32-비트 정수 6초 제한, 데이터 타입은 int 또는 Integer형
5. 우선 순위 큐(최소힙, 최대힙 각각 하나) 두 개가 필요하다.

6. 추가적으로 추가, 삭제한 수들을 관리할 map이 필요하다 -> 이 부분 때문에 1차 삽질함

문제, 입출력, 테스트케이스

후 한 달 만에 드디어 풀었다. 이 문제 붙잡고 있느라 사실상 하루 꼬박 걸린 것 같다.

 

<문제 접근/풀이과정>
1. I value -> value 넣기
2. D -1 -> 최솟값 빼기
3. D 1 -> 최댓값 빼기
4. k <= 1,000,000, 값들은 32-비트 정수 6초 제한, 데이터 타입은 int 또는 Integer형
5. 우선 순위 큐(최소힙, 최대힙 각각 하나) 두 개가 필요하다.
6. 추가적으로 추가, 삭제한 수들을 관리할 map이 필요하다 -> 이 부분 때문에 삽질함 문제명이 이중 우선순위큐라 오로지 우선순위 큐로만 풀고자 했었다 ㅜㅜ

 

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Boj_7662 {
	public static void main(String[] args) throws NumberFormatException, IOException {

		// 1. I value -> value 넣기
		// 2. D -1 -> 최솟값 빼기
		// 3. D 1 -> 최댓값 빼기
		// 4. k <= 1,000,000, 값들은 32-비트 정수 6초 제한
		// 5. 큐 두개
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringTokenizer stz;
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			PriorityQueue<Integer> pqAsc = new PriorityQueue<>();
			PriorityQueue<Integer> pqDesc = new PriorityQueue<>(Collections.reverseOrder());
			TreeMap<Integer, Integer> tm = new TreeMap<>();

			int size = 0;
			for (int j = 0; j < N; j++) {
				stz = new StringTokenizer(br.readLine());
				String key = stz.nextToken();
				int value = Integer.parseInt(stz.nextToken());

				if (key.equals("I")) {// 값 넣기
					size++; // 들어있는 size의 크기 넣기
					pqAsc.offer(value);
					pqDesc.offer(value);
					// 이전에 등록한 값이 있으면 +1, 없으면 1로 등록하기
					tm.put(value, tm.get(value) == null ? 1 : tm.get(value) + 1);
				} else { // 값 빼기
					// 이미 큐에 쓸 수 있는 수가 없는 경우(size = 0)
					if (size == 0) {
						// 각 자료구조 싹 비우기
						pqAsc.clear();
						pqDesc.clear();
						tm.clear();
						continue;
					} else {
						if (value == -1) {// 최솟값 빼기
							int min;
							while(!pqAsc.isEmpty()) {
								min = pqAsc.poll();
								if(tm.get(min)>0) {// 빼낼 수 있는 숫잔지 확인
									tm.put(min, tm.get(min) - 1);
									break;
								}
							}
							size--;
						} else { // 최댓값 빼기
							int max;
							while(!pqDesc.isEmpty()) {
								max = pqDesc.poll();
								if(tm.get(max)>0) {// 빼낼 수 있는 숫잔지 확인
									tm.put(max, tm.get(max) - 1);
									break;
								}
							}
							size--;
						}
					}
				}
			}
			boolean chk = false;
			int min = 0;
			int max = 0;
			while (!pqAsc.isEmpty()) {
				int temp = pqAsc.poll();

				if (tm.get(temp) > 0) {
					chk = true;
					min = temp;
					break;
				}
			}
			if (chk) { // 최솟값 존재한다면
				while (!pqDesc.isEmpty()) {
					int temp = pqDesc.poll();

					if (tm.get(temp) > 0) {
						max = temp;
						break;
					}
				}
				
				sb.append(max).append(" ").append(min).append("\n");
			}else {
				sb.append("EMPTY\n");
			}
		}
		sb.setLength(sb.length()-1);
		System.out.println(sb);
	}
}