[백준] 7662 이중 우선순위 큐

문제

---

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다. 

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자. 

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

 

 

 

 

풀이

---

문제의 제목대로 이중 우선순위 큐를 사용해서 문제풀이를 하였는데, 풀이를 찾아보니 한개 더있었다.

 

풀이방법

1. 우선순위 큐 두개와 맵 사용

2. TreeMap 사용

 

1번 방법 부터 풀이를 하면

오름차순으로 정렬 된 우선순위큐, 내림차순으로 정렬 된 우선순위 큐

두개가 필요하다.

 

이 경우에는 한쪽에서 삭제를 할경우 다른 한쪽의 데이터는 그대로 남아있다.

이를 해결하기 위해서 Map을 이용하여 해당 수가 남아있는지를 판단한다.

 

해당 수가 1개남은 경우에는 Map 에서 지워준다.

<이중 우선순위 큐와 맵사용>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static PriorityQueue<Integer> desc, asc;
	static HashMap<Integer, Integer> map;
	static StringBuilder sb = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = parseInt(br.readLine());
		while(T-->0) {
			
			int k = parseInt(br.readLine());
			
			desc = new PriorityQueue<>();
			asc = new PriorityQueue<>(Collections.reverseOrder());
			map = new HashMap<>();
			
			for(int i = 0 ; i < k ; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				
				char order = st.nextToken().charAt(0);
				
				int num = parseInt(st.nextToken());
				
				switch(order) {
				
				case 'I':
					desc.add(num);
					asc.add(num);
					map.put(num, map.getOrDefault(num, 0) + 1);
					break;
				case 'D':
					delete(num);
					break;
				}
			}
			
			if(map.size() == 0) {
				sb.append("EMPTY\n");
			}
			else {	
				int res = delete(1);
				sb.append(res +" ");
				if(map.size() > 0) { res = delete(-1);}
				sb.append(res + "\n");
			}
		}
		
		System.out.println(sb);
	}
	
	static int delete(int order) {
		int now = 0;
		if(order == 1) {
			if(asc.isEmpty()) { return now;}
			now = asc.poll();			
			while(!map.containsKey(now) && !asc.isEmpty()) {				
				now = asc.poll();
			}
		}
		else {
			if(desc.isEmpty()) { return now;}
			now = desc.poll();
			while(!map.containsKey(now) && !desc.isEmpty()) {				
				now = desc.poll();
			}
		}
		
		if(map.containsKey(now)) {			
			if(map.get(now) == 1) {
				map.remove(now);
			}
			else {
				map.put(now, map.get(now) - 1);
			}			
		}
		
		return now;
	}
}

 

 

2번 풀이다.

TreeMap을 이용하면 코드가 훨씬 쉬워진다.

TreeMap은 Key를 기준으로 오른차순 정렬을 이미 하게 된다.

 

TreeMap의 firstKey(), lastKey() 메서드를 이용하면 편하게 풀수있다.

 

firstKey 는 말 그대로 정렬된 상태의 가장 앞에 있는 Key값을 가져온다.

lastKey 도 말 그대로 정렬된 상태의 가장 뒤에 있는 Key값을 가져온다.

 

이를 이용하면 숫자를 하나 삭제하면 최솟값 큐, 최댓값 큐 에 있는 값을 모두 삭제하는 기능을 구현할 수 있다.

 

<TreeMap 사용 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	
	static TreeMap<Integer, Integer> pq;
	static StringBuilder sb = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = parseInt(br.readLine());
		while(T-->0) {
			
			int k = parseInt(br.readLine());
			
			pq = new TreeMap<>();
			
			for(int i = 0 ; i < k ; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				
				char order = st.nextToken().charAt(0);
				
				int num = parseInt(st.nextToken());
				
				switch(order) {
				
				case 'I':
					pq.put(num, pq.getOrDefault(num,0) + 1);
					break;
				case 'D':
					delete(num);
					break;
				}
			}
			
			if(pq.isEmpty()) {
				sb.append("EMPTY\n");
			}
			else {	
				sb.append(pq.lastKey()).append(" ").append(pq.firstKey()).append("\n");
			}
		}
		
		System.out.println(sb);
	}
	
	static void delete(int order) {
		if(pq.isEmpty()) {return;}
		
		if(order == 1) {
			int key = pq.lastKey();
			if(pq.get(key) == 1) {
				pq.pollLastEntry();
			}
			else {
				pq.put(key, pq.get(key) - 1);
			}
		}
		else {
			int key = pq.firstKey();
			if(pq.get(key) == 1) {
				pq.pollFirstEntry();
			}
			else {
				pq.put(key, pq.get(key) - 1);
			}
		}
	}
}