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

 

처음에는 아래와 같이 무식하게 priorityQueue를 3개 만들어서 기본 pq는 다 poll을 해주고, 1과 -1일 경우 min과 max의 값을 poll해주었다. 이러한 방식으로 문제를 풀게되니 출력초과라는 결과가 나왔다.

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

public class p7662 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		PriorityQueue<Integer> minPq = new PriorityQueue<Integer>();
		PriorityQueue<Integer> maxPq = new PriorityQueue<Integer>(Collections.reverseOrder());

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

		for (int i = 0; i < a; i++) {
			int n = Integer.parseInt(br.readLine());
			for (int j = 0; j < n; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());

				String idx = st.nextToken();
				int num = Integer.parseInt(st.nextToken());

				if (idx.equals("I")) {
					pq.add(num);
					maxPq.add(num);
					minPq.add(num);
				} else {
					if (pq.isEmpty()) {
						continue;
					}
					if (num == 1) {
						pq.poll();
						maxPq.poll();
					} else {
						pq.poll();
						minPq.poll();
					}
				}
			}

			if (pq.isEmpty()) {
				System.out.println("EMPTY");
			} else {
				System.out.println(maxPq.poll() + " " + minPq.poll());
			}
		}
		System.out.println(pq);
	}
}

 

그래서 비슷한 방식으로 내장함수인 remove를 이용하여 기존 pq 대신 min/max pq의 값을 지워주는 방식으로 코드를 작성하였을 때는 시간초과가 나왔다.

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

public class p7662 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		PriorityQueue<Integer> minPq = new PriorityQueue<Integer>();
		PriorityQueue<Integer> maxPq = new PriorityQueue<Integer>(Collections.reverseOrder());

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

		for (int i = 0; i < a; i++) {
			int n = Integer.parseInt(br.readLine());
			for (int j = 0; j < n; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());

				String idx = st.nextToken();
				int num = Integer.parseInt(st.nextToken());

				if (idx.equals("I")) {
					maxPq.add(num);
					minPq.add(num);
				} else {
					if (maxPq.isEmpty()) {
						continue;
					}
					if (num == 1) {
						int k = maxPq.poll();
						minPq.remove(k);
					} else {
						int k = minPq.poll();
						maxPq.remove(k);
					}
				}
			}

			if (maxPq.isEmpty()) {
				System.out.println("EMPTY");
			} else {
				System.out.println(maxPq.poll() + " " + minPq.poll());
			}
		}
	}
}

 

 

그래서 다른 풀이들을 참고하다가 TreeMap이라는 자료형을 알게되었고, 이 방식으로 문제를 풀었다.

트리맵은 레드블랙트리 기반이므로 시간복잡도가 O(logN)이기 때문에 시간제한에 걸리지 않고 문제를 풀 수 있었다.

TreeMap이라는 자료형을 처음 써봐서 사용법이 잘 익진 않았지만, firstKey와 lastKey 값을 직접 꺼낼 수 있었고, 같은 값이 다시 입력으로 들어오면 해당 key의 value를 1 증가시켜주고, 같은 값이 여러 개인 경우 1을 감소시키는 식으로 문제를 해결하였다. treeMap 내장 함수인 getOrDefault를 이용해 값이 없는 경우는 0을 넣어 null값이 되지 않게 해주는 점도 주의해주어야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class p7662 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		for (int i = 0; i < a; i++) {
			TreeMap<Integer, Integer> map = new TreeMap<>();
			int n = Integer.parseInt(br.readLine());
			for (int j = 0; j < n; j++) {
				StringTokenizer st = new StringTokenizer(br.readLine());

				String idx = st.nextToken();
				int num = Integer.parseInt(st.nextToken());

				if (idx.equals("I")) {
					map.put(num, map.getOrDefault(num, 0) + 1);
				} else {
					if (map.isEmpty()) {
						continue;
					}
					if (num == 1) {
						if (map.get(map.lastKey()) == 1) {
							map.remove(map.lastKey());
						} else {
							map.put(map.lastKey(), map.get(map.lastKey()) - 1);
						}
					} else {
						if (map.get(map.firstKey()) == 1) {
							map.remove(map.firstKey());
						} else {
							map.put(map.firstKey(), map.get(map.firstKey()) - 1);
						}
					}
				}
			}

			if (map.isEmpty()) {
				System.out.println("EMPTY");
			} else {
				System.out.println(map.lastKey() + " " + map.firstKey());
			}
		}
	}
}