[알고리즘] Java / 백준 / 이중 우선순위 큐 / 7662

[알고리즘] Java / 백준 / 이중 우선순위 큐 / 7662

문제

문제 링크

접근 방식

단순히 최대 힙과 최소 힙을 만든 후 각각 힙에서 최대,최솟값을 뺄 때 다른 우선순위 큐의 값을 제거해주는 방식을 사용하면 시간초과가 난다.

때문에 HashMap 자료구조로 현재 가지고 있는 수를 체크하고, 최대, 최솟값을 뺄 때 Map의 데이터를 보아 각 힙의 peek가 Map에 없다면 동기화를 위해 반복적으로 poll 해준 후 최대, 최솟값을 뺀다.

마지막 출력할 때도 동기화를 해준 후 emtpy 혹은 최대, 최솟값을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_7662 {

	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++) {
			int k = Integer.parseInt(br.readLine());
			
			PriorityQueue<Integer> pq = new PriorityQueue<>();
			PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
			
			HashMap<Integer,Integer> map = new HashMap<>();
			
			for(int j = 0;j< k;j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				char command = st.nextToken().charAt(0);
				int num = Integer.parseInt(st.nextToken());
				
				
				
				if(command == 'I') {
					pq.offer(num);
					maxPq.offer(num);
					map.put(num, map.getOrDefault(num, 0)+1);
				}
				else {
					
					if(num == 1) {
						while(!maxPq.isEmpty()&&map.get(maxPq.peek()) == null) {
							maxPq.poll();
						}
						if(maxPq.isEmpty()) continue;
						int delNum = maxPq.poll();
						if(map.get(delNum) == 1) map.remove(delNum);
						else if(map.get(delNum) > 1) map.put(delNum, map.get(delNum)-1);
						
					}
					else {
						while(!pq.isEmpty()&&map.get(pq.peek()) == null) {
							pq.poll();
						}
						if(pq.isEmpty()) continue;
						int delNum = pq.poll();
						if(map.get(delNum) == 1) map.remove(delNum);
						else if(map.get(delNum) > 1) map.put(delNum, map.get(delNum)-1);
					}
				}
			}
			while(!maxPq.isEmpty()&&map.get(maxPq.peek()) == null) {
				maxPq.poll();
			}
			while(!pq.isEmpty()&&map.get(pq.peek()) == null) {
				pq.poll();
			}
			
			if(pq.isEmpty()) sb.append("EMPTY\n");
			else{
				
				
				sb.append(maxPq.poll() + " " +  pq.poll() + "\n");
			}
		}
		System.out.print(sb);
	}
}