BOJ - 이중 우선순위 큐

7662 이중 우선순위 큐 : https://www.acmicpc.net/problem/7662

---

Problem

---

Solve

TreeMap으로 구현이 가능하지만 많은 분들이 풀어서, 최대힙과 최소힙을 이용하여 문제를 구현하였습니다.

최대힙, 최소힙을 이용하여 풀때 두 힙을 동기화 시켜주는 것이 중요합니다. 이 기능을 Map을 이용해줍니다.
Map에는 값을 저장해줄때 해당 값의 개수를 증가시켜주고 삭제하는 경우 해당 값을 감소시켜주고 0이 된 경우 Map에서 삭제시켜줍니다.

Insert인 경우 최대힙과 최소힙에 해당 값을 저장해줍니다.
그리고 최대힙과 최소힙의 동기화를 위해 Map을 이용하여 해당 값을 저장하고 value에 개수를 증가시켜줍니다.

Delete에서 최대값을 삭제하는 경우, 최대힙에서 우선순위가 가장 높은 값을 가져옵니다.
꺼내온 값이 Map에 존재한다면 해당 값을 삭제시켜주고 존재하지 않는다면, 최소힙에서 삭제한 값이기 때문에 최대힙에서 다음값을 꺼내와 위 과정을 반복해줍니다.

최소값을 삭제하는 경우에도 Map에 꺼내오는 값의 존재여부를 확인하고 위와 같은 과정을 반복해줍니다.

모든 연산을 끝냈다면 최대힙과 최소힙에 있는 값을 반환해주는데, 이때도 최대힙과 최소힙이 동기화 되어있지 않은 경우가 있을 수 있습니다. 그렇기 때문에 각 힙에서 값을 꺼내오는 값을 Map에 존재여부를 확인하여 동기화 시켜주면서 값을 반환해줍니다.

---

Code

import java.io.*;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
import java.util.Map;
import java.util.HashMap;
import java.util.Comparator;
public class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T-- > 0){
			MyQueue queue = new MyQueue();
			int k = Integer.parseInt(br.readLine());

			for(int i=0;i<k;i++){
				StringTokenizer st = new StringTokenizer(br.readLine()," ");
				String operation = st.nextToken();
				int n = Integer.parseInt(st.nextToken());

				if(operation.equals("I")){
					queue.input(n);
				}else{
					queue.delete(n);
				}
			}

			if(queue.size == 0){
				sb.append("EMPTY");
			}else{
				sb.append(queue.getMax()).append(" ").append(queue.getMin());
			}
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static class MyQueue{
		PriorityQueue<Integer> maxQueue;
		PriorityQueue<Integer> minQueue;
		Map<Integer, Integer> map;
		int size;

		public MyQueue(){
			this.map = new HashMap<>();
			this.maxQueue = new PriorityQueue<>(Comparator.reverseOrder());
			this.minQueue = new PriorityQueue<>();
			this.size = 0;
		}

		public void input(int v){
			this.maxQueue.offer(v);
			this.minQueue.offer(v);
			this.size++;
			this.map.put(v, map.getOrDefault(v, 0)+1);
		}

		public void delete(int type){
			if(size == 0) return;

			if(type == 1){
				removeNotExist(maxQueue);
                /*
                removeNotExist를 통해 존재하는 값을 꺼내올 수 있습니다.
                또한 값이 존재하지 않는 경우 삭제하는 예외를 처리하였기 때문에 힙에서 값을 꺼내올때 NPE가 발생하지 않습니다.
                */
				int out = this.maxQueue.poll();
				map.put(out, map.get(out)-1);
				if(map.get(out)==0) map.remove(out);
			}else{
				removeNotExist(minQueue);
				int out = this.minQueue.poll();
				map.put(out, map.get(out)-1);
				if(map.get(out)==0) map.remove(out);
			}

			this.size--;
		}

		public int getMax(){
			removeNotExist(maxQueue);
			return this.maxQueue.peek();
		}

		public int getMin(){
			removeNotExist(minQueue);
			return this.minQueue.peek();
		}

		//힙에서 꺼내오려는 값이 Map에 존재하는지 확인하고 존재할때까지 반복합니다.
		public void removeNotExist(PriorityQueue<Integer> pq){
			while(!map.containsKey(pq.peek())){
				pq.poll();
			}
		}
	}
}

---

Result

---

Reference

https://gooweon.tistory.com/115

---