No7662 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

 

두개의 PriorityQueue를 활용해서 하나는 최대값을 앞에 하나는 최소값을 앞에 두는 queue를 활용하면 될 것 같았다. 그래서 입력 값을 받으면 두 queue에 넣고 최대값을 빼라는 명령이 있으면 최대값queue는 poll을 최소값queue는 remove 메소드를 쓰면 될 것 같았다. 코드는 아래와 같다.

 

package com.yuk;

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

public class No7662 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < T; i++) {
			int k = Integer.parseInt(br.readLine());
			PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
			PriorityQueue<Integer> minQ = new PriorityQueue<>();
			
			while(k-- >0) {				
				
				String[] strArr = br.readLine().split(" ");
				
				if(strArr[0].equals("I")) {
					int in = Integer.parseInt(strArr[1]);
					maxQ.add(in);
					minQ.add(in);
				}else {
					int out = Integer.parseInt(strArr[1]);
					if(strArr[1].equals("1")) {
						minQ.remove(maxQ.poll());
					} else {
						maxQ.remove(minQ.poll());
					}
				}
				
			}
			
			if(maxQ.isEmpty()) {
				sb.append("EMPTY");
			} else {
				sb.append(maxQ.poll()).append(" ").append(minQ.poll());
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}

}

하지만 remove 메소드 방식이 queue 의 모든 수를 순서대로 검색하는 것이기 때문에 시간 초과가 난다. 그래서 maxQ에서 최솟값을 삭제하는 것과 minQ에서 최대값을 삭제하는 방식의 성능을 좀 더 높일 필요가 있는 것 같다. 그래서 이리저리 시도해 보았지만 실패.. 그래서 구글링을 해서 찾아보았다.

 

https://girawhale.tistory.com/14

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

 

1. HashMap을 사용해서 실제로 남아 있는 입력값과 그 개수를 담는다.

2. maxQ와 minQ는 입력 값이 올 때 모두 입력 받고 빼낼 때는 remove 메소드를 통해 빼낸다.

3. remove 메소드 로직은 최대값을 삭제하라는 입력이 오면 maxQ에서 poll을 하여 그 값이 map에 있을 경우 그 갯수를 줄이거나 1개인 경우 없앤다. 없다면 다시 poll을 하여서 map에 있는 값이 나올 때까지 반복한다.(remove할 경우 maxQ나 minQ만 값을 삭제하기 때문에 한번에 삭제하지 못했던 값을 삭제하는 과정이다)

public static int remove(Queue<Integer> queue, Map<Integer, Integer> map) {
		
		int num;
		while(true) {
			num = queue.poll();
			int cnt = map.getOrDefault(num,0);
			if(cnt == 0) continue;
			else if(cnt == 1) map.remove(num);
			else {
				map.put(num, cnt-1);			
			}
			break;
		}
		
		return num;
		
	}

전체 소스 코드는 아래와 같다.

package com.yuk;

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

public class No7662 {
	
	public static int remove(Queue<Integer> queue, Map<Integer, Integer> map) {
		
		int num;
		while(true) {
			num = queue.poll();
			int cnt = map.getOrDefault(num,0);
			if(cnt == 0) continue;
			else if(cnt == 1) map.remove(num);
			else {
				map.put(num, cnt-1);			
			}
			break;
		}
		
		return num;
		
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < T; i++) {
			int k = Integer.parseInt(br.readLine());
			Map<Integer, Integer> map = new HashMap<>();
			PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
			PriorityQueue<Integer> minQ = new PriorityQueue<>();
			
			while(k-- >0) {				
				
				String[] strArr = br.readLine().split(" ");
				
				if(strArr[0].equals("I")) {
					int in = Integer.parseInt(strArr[1]);
					map.put(in, map.getOrDefault(in, 0) + 1);
					maxQ.add(in);
					minQ.add(in);
				}else {
					if(map.size()!=0) {
						if(strArr[1].equals("1")) {
							remove(maxQ, map);
						} else {
							remove(minQ, map);
						}
					}
				}
				
//				System.out.print("map ");
//				for (int a : map.keySet()) {
//					System.out.print(" "+a);
//				}
//				System.out.println();
//				System.out.print("max ");
//				for (int a : maxQ) {
//					System.out.print(" "+a);
//				}
//				System.out.println();
//				System.out.print("min ");
//				for (int a : minQ) {
//					System.out.print(" "+a);
//				}
			}
			
			if(map.isEmpty()) {
				sb.append("EMPTY");
			} else if(map.size()==1) {
				int max = remove(maxQ, map);
				sb.append(max).append(" ").append(max);
			}else {
				int max = remove(maxQ, map);
				int min = remove(minQ, map);
				sb.append(max).append(" ").append(min);
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
	}

}