백준 7662번 : 이중 우선순위 큐 (Java)

 문제

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

7662번: 이중 우선순위 큐

7662 이중 우선순위 큐

 

 구현 방법

최댓값, 최솟값을 삭제할 때마다 바로 빼낼 수 있도록 최댓값 우선순위 큐와 최솟값 우선순위 큐로 나누어 풀어줬습니다.

만약 최댓값을 삭제한 경우 최솟값 우선순위 큐에 값이 남아있습니다.

어떤 값이 삭제 되었는지 최솟값 우선순위 큐가 알아야 하므로 맵에 삭제된 값을 저장해주었습니다.

(동일한 정수가 삽입될 수 있으므로 개수도 같이 저장하기 위해 맵을 사용했습니다)

 

 

구현 과정을 단계별로 간략하게 나타내면

1. 큐에 삽입 시 최댓값 우선순위 큐와 최솟값 우선순위 큐에 모두 삽입
2. 최댓값 또는 최솟값 삭제 시 (최솟값 예시)
2-1) 삭제할 값을 꺼내  최댓값 삭제 맵에 값이 있는지 확인=
2-2) 맵에 있다면 개수 체크하여 맵에서 삭제 또는 개수 줄여주기
2-3) 맵에 없다면 삭제 가능 -> 최솟값 삭제 맵에 추가
3. 연산이 모두 끝났지만 미처 삭제되지 못한 값이 있을 수 있으므로 다시 체크

 

* 주의할 점 *

- 값이 중복될 수 있음

- 연산이 끝나도 최댓값, 최솟값이 이미 삭제되었을 수 있음 -> 다시 삭제된 값인지 확인 필요

 

 구현 코드

package BOJ.Gold;

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.StringTokenizer;

public class B7662_이중우선순위큐 {
	static int TC, K, value;
	static char menu;
	static PriorityQueue<Integer> MIN = new PriorityQueue<>(), MAX = new PriorityQueue<>(Collections.reverseOrder());
	// 최솟값 삭제 저장, 최댓값 삭제 저장
	static Map<Integer, Integer> minMap = new HashMap<>(), maxMap = new HashMap<>();
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = null;
		TC = Integer.parseInt(br.readLine());
		while(TC-->0) {
			K = Integer.parseInt(br.readLine());
			for (int i=0;i<K;i++) {
				st = new StringTokenizer(br.readLine());
				menu = st.nextToken().charAt(0);
				value = Integer.parseInt(st.nextToken());
				switch(menu) {
				case 'I':
					// 최댓값, 최솟값 우선순위 큐에 모두 저장
					MIN.offer(value);
					MAX.offer(value);
					break;
				case 'D':
					if (value == 1) check(false, MAX, MIN, maxMap, minMap);
					else check(false, MIN, MAX, minMap, maxMap);
					break;
				}
			}
			
			// 미처 못지운 값이 있을 수 있으므로 삭제해줌
			check(true, MAX, MIN, maxMap, minMap);
			check(true, MIN, MAX, minMap, maxMap);
			
			if (MAX.size() == 0) sb.append("EMPTY\n");
			else sb.append(MAX.peek()+" "+MIN.peek()+"\n");
			// 초기화
			minMap.clear();
			maxMap.clear();
			MIN.clear();
			MAX.clear();
		}
		System.out.println(sb);
	}
	
	static void check(boolean flag, PriorityQueue<Integer> now, PriorityQueue<Integer> other, Map<Integer, Integer> nowMap, Map<Integer, Integer> otherMap) {
		// 최솟값 삭제 예시
		while(!now.isEmpty()) {
			int poll = now.poll(); // 삭제할 값 꺼내기
			// 최댓값에서 이미 삭제한 값이라면
			if (otherMap.containsKey(poll)) {
				int cnt = otherMap.get(poll)-1;
				if (cnt == 0) otherMap.remove(poll); // 더 이상 존재하지 않는다면 삭제
				else otherMap.put(poll, cnt);
			} else { // 삭제한 값이 아니라면
				// 마지막에 삭제 체크 해주는 것이라면 삭제할 값이 없으므로 다시 큐에 삽입
				if (flag) now.offer(poll);
				// 최솟값을 삭제하는 것이라면 최솟값 삭제 맵에 해당 값 추가
				else nowMap.put(poll, nowMap.containsKey(poll)?nowMap.get(poll)+1:1);
				return;
			}
		}
	}
}

 

정답!