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

문제

 

 

접근 방식

우선순위 큐를 활용해서 풀 수 있는 문제로 우선순위 큐를 덱처럼 사용하면 된다.

 

원할 때마다 언제든지 가장 작은 값을 빼거나 가장 큰 값을 뺄 수 있어야 하기 때문에

최소힙과 최대힙에 동일하게 수를 추가해 준 후에

가장 큰 값을 빼야 하는 경우에는 최대힙에서 반대의 경우는 최소힙에서 빼주면 된다.

 

이때 조심해야할게 반대쪽에서 뺀 수는 반대쪽에만 사라지고 다른 한쪽에는 존재하기 때문에

맵을 이용해서 수마다 등장 횟수를 카운팅 해준 후에 수들을 큐에서 꺼낼 때마다

꺼낸 수가 등장 횟수가 남아있는지 확인하여 다른 쪽의 큐와 상태를 유지해 줄 수 있다.

 

예를 들면 최대값을 하나 빼려고 최대힙에서 9라는 숫자를 꺼냈는데

해당 숫자의 카운트가 0이라면 최소힙에서 빼서 사라진 값이기에

해당 수를 건너 뛰고 최대힙에서 카운트가 0이 아닌 수를 찾을 때까지

계속해서 수를 꺼내주면 된다.

 

풀이

public class Main {

	private static HashMap<Integer, Integer> countMap;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		while (t-- > 0) {
			int k = Integer.parseInt(br.readLine());

			PriorityQueue<Integer> minQ  = new PriorityQueue<>();
			PriorityQueue<Integer> maxQ  = new PriorityQueue<>(Collections.reverseOrder());
			countMap = new HashMap<>();

			while (k-- > 0) {
				st = new StringTokenizer(br.readLine());

				String command = st.nextToken();
				int n = Integer.parseInt(st.nextToken());

				if (command.equals("I")) {
					minQ.offer(n);
					maxQ.offer(n);
					countMap.put(n, countMap.getOrDefault(n, 0) + 1);
					continue;
				}

				if (countMap.isEmpty()) continue;

				poll(n > 0 ? maxQ : minQ);
			}

			if (countMap.isEmpty()) sb.append("EMPTY").append("\n");
			else {
				int max = poll(maxQ);
				sb.append(max).append(" ").append(countMap.isEmpty() ? max : poll(minQ)).append("\n");
			}
		}

		System.out.println(sb);
	}

	private static int poll(PriorityQueue<Integer> pq) {
		int num = 0;

		while (true) {
			num = pq.poll();
			int count = countMap.getOrDefault(num, 0);

			if (count == 0) continue;

			if (count == 1) countMap.remove(num);
			else countMap.put(num, count - 1);

			break;
		}

		return num;
	}
}