BOJ - 7662 ) 이중 우선순위 큐

---

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

7662번: 이중 우선순위 큐

---

솔직히 우선순위큐 2개로 풀려했지만 실패했다.. 시간초과가 계속뜨길래 풀이를 참고하니 

 

Treemap으로 간단하게 푸는 풀이가 대세였다..

 

Treemap에 대한설명은 구글에 잘 되어있는 자료가 많지만 

 

간단하게 key는 오름차순으로 정렬되며 중간 삭제나 lastget , firstkey로 처음과 끝을 가져 올 수 있는 편리한

자료구조이다.

 

Hashmap 저격데이터가 들어있는경우가 많아서 map자료구조는 생각못했는데 자주이용해봐야겠다..

---

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

public class BOJ_7662 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		int tc = Integer.parseInt(st.nextToken());
		
		for(int t=0;t<tc;t++) {
			
			st    = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			TreeMap<Integer, Integer> tm = new TreeMap<>();
			for(int i=0;i<n;i++){
				
				st     = new StringTokenizer(br.readLine());
				char c = st.nextToken().charAt(0);
			    int  m = Integer.parseInt(st.nextToken());
			    
				if(c=='I') {
					if(tm.getOrDefault(m, 0)==0) {
						tm.put(m, 1);
					} else {
						tm.put(m, tm.get(m)+1);
					}
				} else {
					if(tm.keySet().size()==0) {
						continue;
					}
					if(m==1){
						int l = tm.lastKey();
						if(tm.get(l) > 1) {
						    tm.put(l, tm.get(l)-1);
						} else {
							tm.remove(l);
						}
					} else {
						int f = tm.firstKey();
						if(tm.get(f) > 1) {
						    tm.put(f, tm.get(f)-1);
						} else {
							tm.remove(f);
						}
					}
				}
			}
			
			if(tm.keySet().size()==0) {
				sb.append("EMPTY\n");
			} else {
				sb.append(tm.lastKey()+" "+tm.firstKey()+"\n");
			}
		}
		System.out.println(sb.toString());
	}
}

---