[Java]백준 BaekJoon.AC 7662 : 이중 우선순위 큐 (3%에서 틀렸다)

<병아리의 고뇌와 눈물이 서려있는 슬픈 글>

 

---

 

 

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

7662번: 이중 우선순위 큐

 

 

 

이중 우선순위 큐 문제..

처음엔 PriorityQueue로 풀었는데 최소값과 최대값을 자유자재로 삭제하는게 어려워 방법을 전환했다.

인터넷도 참고해서 야심차게 TreeMap에 처음 도전했는데, 기존에 사용해봤던 HashMap과 비슷해 코딩 자체는 크게 어렵진 않았다.

(다만 구현이 안될뿐,,)

 

이것 저것 알아가며 대장정 끝에 코드를 구현했다.

작동도 잘 되고 예제도 척척 풀어내길래 잔뜩 기대하며 제출했는데.

애초에 느리던 채점이 1%인가... 3%였던가? 무튼 뚝 끊겼다. 틀리면 아예 틀렸지 개미만큼 맞은게 더 속상했다,,,,ㅋㅋㅋ

예제만 맞은 수준인가ㅠㅅㅠ

 

인터넷에 코딩고수들이 올려준 코드를 참고해 더 다듬었다.

말이 다듬는 거지 (초보자인 내 생각으론 성능이 같지만) 틀린 부분을 모르니 그냥 전체적으로 비슷하게 옮겨 적었다.

그런데도 3%에서 나아갈 생각이 없다. (역시 성능은 같고 방법만 달랐던 건가!  괜히 고쳤, 그래도 다행이었다)

내가 어디 치명적인 결함을 놓친거 같은데 도통 모르겠다.

예제라도 안돌아가면 찾을 텐데 예제 답은 척척 뽑아내고,, 반례도 못찾겠음.

StringTokenizer사용할 때 String배열로 연산과 숫자를 쪼개시던데 이것도 따라해볼까 하다 관뒀다.

 

잠깐 오류인가 싶어 다른 사람 코드를 그대로 복붙해 제출하니 냉큼 맞았다고 축하해주더라^^

---

이 녀석이 내가 티스토리를 시작하게 만들었다.

혹시라도 오류를 발견하셨다면 꼭 댓글로...

 

 

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));
    	StringBuilder sb = new StringBuilder();
    	
    	int T = Integer.parseInt(br.readLine());
    	
    	for(int i=0; i<T; i++) {
    		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
    		int k = Integer.parseInt(br.readLine());
    		
    		for(int j=0; j<k; j++) {
    			StringTokenizer st = new StringTokenizer(br.readLine());
    			String ID = st.nextToken();
    			int n = Integer.parseInt(st.nextToken());
    			
    			if(ID.equals("I")) {
    				map.put(n, map.getOrDefault(n, 0)+1);
    				
    			}else {
    				if(map.size()==0) continue;
    				
    				if(n==1){
    					int last = map.lastKey();
    					
    					if(map.get(last)==1) {
    						map.remove(last);
    					}else {
    						map.put(last, map.get(last)-1);
    					}
    					
    				}else {
    					int first = map.firstKey();
    					
    					if(map.get(first)==1) {
    						map.remove(first);
    					}else {
    						map.put(first, map.get(first)-1);
    					}
    				}
    			}
    			
    		}
    		
    		if(map.size()==0) {
    			sb.append("EMPTY\n");
    		}else {
    			sb.append(map.lastKey()+" " + map.firstKey()+"\n");
    		}
    		System.out.println(sb.toString());
    	}
	}
}