백준 - 이중 우선순위 큐 ( 7662번, JAVA )

Queue ( https://www.acmicpc.net/problem/7662 )

풀이

일단 시간초과 해결하는데 제출한 시도 횟수다 🤣

• 먼저 Scanner를 사용해서 우선순위큐를 2개 만들어서 내림차순, 오름차순으로 뽑아 마지막에 각각 하나씩 출력해줬다. 근데 풀면서 골드인데 너무 간단한데...? 이런 생각이 들어서 제출해보니 역시 시간초과 뜨고 혹시 입력을 Scanner말고 버퍼더 리더 쓰면 해결이 될까 했지만 1퍼센트에서 시간초과가 떴더 😂

• 그래서 어떻게 해야할지 고민하던중 문제 태그에 트리가 있었다. 트리맵에 가장 작은키와 가장 큰 키를 찾을 수 있는 메소드가 있었다. 문제에 같은수가 있다면 하나만 뽑고 나머지는 유지해야하기에 key에 숫자를 넣고 value에 개수를 넣어줬다. -> val-- 해주는 부분

• 이후 마지막에 비어있다면 "EMPTY"를 출력해주고 아니라면 각각 최대, 최소를 출력해줬다.

• 근데 여기서 45%에서 Nullpointer가 발생했다.. 대체 뭐지 .. 하다가 가장 큰 값을 뽑았는데 만약 트리맵이 비어있다면 ? 그럼 최대==최소 하나의 수기 때문에 마지막에 다시 한 번 분기해줬다. 트리맵을 활용한 문제도 잘 기억하자 !

• 참고할 것 ) 백준에서 Entry는 java.uil.*; 로 인식이 안된다. 꼭 import java.util.Map.Entry; 이걸 따로 임포트 시켜주자

package problem_solving.queue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeMap;

public class BaekJoon_7662 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 		
		Integer t = Integer.parseInt(br.readLine());
		while(t-- > 0 ) {
			StringBuilder sb = new StringBuilder();
			Integer n = Integer.parseInt(br.readLine());
			TreeMap<Integer, Integer> tm = new TreeMap<>();

			while(n -- > 0 ) {
				String [] input = br.readLine().split(" ");

				if (input[0].equals("I")) {
					Integer num = Integer.parseInt(input[1]);
					if( !tm.containsKey(num)) {
						tm.put(num, 1);
					} else {
						int amount = tm.get(num);
						amount++;
						tm.put(num,amount);
					}
				} else if( input[0].equals("D")) {
					Integer num = Integer.parseInt(input[1]);
					if( tm.isEmpty()) {
						continue;
					}
					if( num < 0 ) {
						Entry<Integer, Integer> FirstEntry = tm.pollFirstEntry();
						Integer val =FirstEntry.getValue() ;
						if( val != 1 ) {
							int key = FirstEntry.getKey();
							val--;
							tm.put(key , val );
						} 
					} else if( num > 0 ){
						Entry<Integer, Integer> LastEntry = tm.pollLastEntry();
						Integer val =LastEntry.getValue() ;
						if( val != 1 ) {
							int key = LastEntry.getKey();
							val--;
							tm.put(key , val );
						} 
					}
				}
				
			}
			if( tm.isEmpty()) {
				System.out.println("EMPTY");
			} else {
				Entry<Integer, Integer> LastEntry = tm.pollLastEntry();
				if( !tm.isEmpty()) {
					Entry<Integer, Integer> FirstEntry = tm.pollFirstEntry();
					System.out.println(LastEntry.getKey()+ " "+ FirstEntry.getKey());
				} else {
					System.out.println(LastEntry.getKey()+ " "+ LastEntry.getKey());
				}

			}
		}

	}

}