백준 7662 - 이중 우선순위 큐 [자바]

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

7662번: 이중 우선순위 큐

---

풀이 과정

최소값과 최대값을 뽑아낼 수 있는 이중 우선순위 큐를 구현하는 문제이다.

 

최소 힙, 최대 힙 2개를 선언해서 풀이하는 방법도 있지만 자바에서는 최소값 반환과 최대값 반환이 O(logN)으로 가능한 이진 검색 트리, 그 중에서도 레드 블랙 트리로 구현된 트리셋 자료구조가 존재해 트리셋 자료구조를 활용해 문제를 해결하였다.

 

트리셋은 Set이므로, 중복된 수를 여러개 담을 수 없기에, 특정 수의 개수를 저장할 해쉬맵을 선언하여 문제를 해결하였다. 소스의 주석을 보면 이해할 수 있다.

---

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	static StringBuilder sb = new StringBuilder();

	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());
			HashMap<Integer, Integer> hm = new HashMap<>(); // 숫자의 개수를 저장할 해쉬맵
			TreeSet<Integer> ts = new TreeSet<>(); // 이중 우선순위 큐 역할을 할 트리셋
			for (int i = 0; i < k; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				String command = st.nextToken();
				int input = Integer.parseInt(st.nextToken());
				
				if (command.equals("I")) { // 입력이면
					// 이미 입력받았던 거면 개수를 증가시킨다
					if (hm.containsKey(input)) hm.put(input, hm.get(input)+1);
					
					// 없었던거면 해쉬맵에 개수 1개로 표시하고 트리셋에 넣는다
					else {
						hm.put(input, 1);
						ts.add(input);
					}
				} else {
					if (ts.isEmpty()) continue; // 비었는데 삭제 연산은 무시
					
					if (input == 1) { // 최대값 출력
						int maxValue = ts.last();
						
						// 같은 수를 2개 이상 담겨있으면 해쉬맵을 보고 개수만 하나 줄여준다
						if (hm.get(maxValue) > 1) hm.put(maxValue, hm.get(maxValue) - 1);
						
						// 아니면 해쉬맵에서 제거하고 트리셋에서도 제거한다
						else {
							ts.pollLast();
							hm.remove(maxValue);
						}
					} else { // 최소값 출력에서도 같은 연산을 수행한다
						int minValue = ts.first();
						if (hm.get(minValue) > 1) hm.put(minValue, hm.get(minValue) - 1);
						else {
							ts.pollFirst();
							hm.remove(minValue);
						}
					}
				}
			}
			
			if (ts.isEmpty()) {
				sb.append("EMPTY");
			} else {
				sb.append(ts.last()).append(' ').append(ts.first());
			}
			
			sb.append('\n');
		}
		
		System.out.print(sb.toString());
	}
}