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

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

7662번: 이중 우선순위 큐

---

[풀이]

 

- 자료구조 유형의 문제입니다.
- 처음에는 이중 우선순위 큐라는 문제를 읽고 우선순위 큐를 두개선언하는 방식을 생각했습니다.
  - 하나는 정방향, 하나는 역방향으로 선언하는 방식으로 말이죠.
  - 그런데, 이렇게 구현을 하려다보니 문제가 발생합니다.
  - 바로, 연산을 모두 마치고 나면, 두개의 큐에 남아있는 데이터가 다릅니다.
- 그래서, TreeMap 자료구조를 이용해서 풀겠습니다.(저도 이번에 공부했습니다.)
- TreeMap은 레드 - 블랙 트리(이진탐색트리 보완)로 이루어져 있습니다. 
- 또한, TreeMap은 값이 삽입 될 때, 정렬된 상태(오름차순)로 유지됩니다.
  - 그래서 TreeMap은 정렬된 데이터를 조회하거나 범위 검색을 할 경우 효율성에서 좋습니다.
- 만약, TreeMap에서 value가 0이 될 경우 키를 삭제하고, 1 이상일 경우에는 여러번 삽입 된 것이기 때문에 값을 1개 제거합니다.
- 연산과정에서는 TreeMap의 firstKey() 메소드와 lastKey() 메소드를 이용해서 최대값, 최소값의 키를 반환하여 활용할 수 있습니다.

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		
		while (t-- > 0) {
			int orderNum = Integer.parseInt(br.readLine());
			TreeMap<Integer, Integer> map = new TreeMap<>();
			
			while (orderNum-- > 0) {
				StringTokenizer st = new StringTokenizer(br.readLine()," ");
				String order = st.nextToken();
				int num = Integer.parseInt(st.nextToken());
				
				if (order.equals("I")) {
					map.put(num,map.getOrDefault(num,0) + 1);
				} else {
					if (map.size() == 0) {
						continue;
					}
					int deleteNumKey = num == -1  ? map.firstKey()  : map.lastKey();
					if (map.get(deleteNumKey) == 1) {
						map.remove(deleteNumKey);
					} else if (map.get(deleteNumKey) > 1) {
						map.put(deleteNumKey,map.get(deleteNumKey) - 1);
					}
				}
			}
			if (map.size() == 0) {
				System.out.println("EMPTY");
			} else {
				System.out.println(map.lastKey() + " " + map.firstKey());
			}
		}
	}
}