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

나의 첫 알고리즘 velog다!

백준 7662번 이중 우선순위큐라는 문제를 풀어보았다.
문제는 아래 캡쳐와 같다.

문제를 처음 봤을 때 나의 생각은
'오 문제 이름 그대로 우선순위큐를 두개 이용하면 되는거 아니야?!' 라고 생각을 했다.
하나는 오름차순, 다른 하나는 내림차순의 우선순위큐로 구현했다.

그러나...결과는 슬펐다.

우선순위큐를 두개로 사용하니까 시간 초과가 나버렸다,,,
이런!!!

알고보니 우선순위큐가 아닌 TreeMap을 사용해야했다.

출처: 코딩팩토리

TreeMap이란 Tree에 기반하여 key와 value값을 저장할 수 있는 Map 컬렉션이다. TreeMap은 데이터를 저장할 때 자동으로 정렬해주기 때문에 해당 문제를 풀 수 있었다. 하지만 이러한 장점이 HashMap보다는 성능이 떨어지게 한다는 점!

import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
	// TODO Auto-generated method stub
	BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
	TreeMap <Integer, Integer> tmap;
	
	int T= Integer.parseInt(br.readLine());//테케 갯수
	for (int tc=0; tc<T; tc++) {
		tmap= new TreeMap<>();
		int k= Integer.parseInt(br.readLine());
		String input;
		StringTokenizer st;
		for (int i=0; i<k; i++) {
			input= br.readLine();
			st= new StringTokenizer(input);
			String token1= st.nextToken();
			String token2= st.nextToken();
			if (token1.equals("I")) {
				tmap.put(Integer.parseInt(token2),tmap.getOrDefault(Integer.parseInt(token2),0)+1);
			}
			else {
				if(tmap.isEmpty()) {
					continue;
				}
				if (token2.equals("-1")) {
					
					int min= tmap.firstKey();
					if (tmap.get(min)==1) {
						tmap.remove(min);
					}
					else {
						tmap.put(min,tmap.get(min)-1 );
					}
					
				}
				else {
					int max= tmap.lastKey();
					if(tmap.get(max)==1) {
						tmap.remove(max);
					}
					else {
						tmap.put(max, tmap.get(max)-1);
					}
				
				}
			}
		}
		if (tmap.isEmpty()) {
			System.out.println("EMPTY");
		}
		else {
			int min= tmap.firstKey();
			int max= tmap.lastKey();
			System.out.println(max+" "+ min);
		}
		
	}

}
}