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

0. 문제 링크

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

7662번: 이중 우선순위 큐

---

1. 문제 핵심

1. 우선순위 큐인데 입력받은 값을 양쪽으로 제거할 수 있어야 합니다.

---

2. 문제 접근

자바의 PriorityQueue는 처음 선언할 때 comparator를 변경할 수 없기 때문에 PQ를 2개 만들던가, 아니면 다른 Collection을 사용해야 한다고 생각은 했습니다.

하지만 PQ를 2개 만들었을 때 가장 높은 데이터를 삭제했을 때 오름차순 PQ에 저장한 해당 데이터를 어떻게 삭제해줄 것이냐를 해결하지 못해서 풀지 못했습니다.'

솔루션을 참고했고 PQ 2개와 Map을 사용한 방법과 TreeMap 하나만 사용하는 풀이 방법이 있었습니다.

1. PQ 2개와 Map을 사용하는 방식은 데이터를 입력할 때마다 Map에 해당 데이터를 +1해주고 데이터를 꺼내줄 때 while로 Map에 1 이상 저장되어있는 값을 꺼낼 때까지 계속 꺼내줍니다.
2. TreeMap을 몰랐다면 이 방법으로 푸는 것이 확실한 것 같습니다.

 

1. TreeMap은 평소에도 가끔 사용하는 콜렉션이었는데 lastKey()와 firstKey()같은 함수가 있는 줄은 몰랐습니다.
2. 선언 방식의 차이였는데 

tree <Integer, Integer> map = TreeMap<>();

이 아닌

TreeMap<Integer, Integer> map = TreeMap<>();;

으로 선언을 해주어야했던 것입니다.

TreeMap은 입력받은 Key 값을 자동으로 정렬해주기 때문에 위의 두 함수와 함께 사용하면 매우 쉽게 문제를 해결할 수 있습니다. 

---

3. 코드 분석

기존에 입력되었다면 기존 값에 1을 더해주고 없다면 1을 넣어줍니다.

첫번째 키와 해당 키를 통해 첫번째 값을 가져오고 해당 숫자가 1개만 있다면 값을 제외해주고 1개 이상 있다면 값을 1개만큼 낮춰줍니다.

---

4. 베스트 코드 분석

1.  

---

5. 코드

package _22_10_18;

import java.io.*;
import java.util.*;

public class BOJ_G4_이중우선순위큐 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		int N, V;
		TreeMap<Integer, Integer> map;
		int left = 0, right = 0;
		for (int i = 0; i < T; i++) {
			map = new TreeMap<>();
			N = Integer.parseInt(br.readLine());
			for (int j = 0; j < N; j++) {
				st = new StringTokenizer(br.readLine());
				// check I or D
				String iOrD = st.nextToken();
				// save I or D
				V = Integer.parseInt(st.nextToken());

				if (iOrD.equals("I")) {
					if (map.get(V) != null)
						map.put(V, map.get(V) + 1);
					else
						map.put(V, 1);
				} else {
					if (map.size() == 0)
						continue;
					if (V == -1) {
						int firstKey = map.firstKey();
						int firstValue = map.get(firstKey);
						if (firstValue == 1) {
							map.remove(firstKey);
						} else {
							map.put(firstKey, firstValue - 1);
						}
					} else {
						int lastKey = map.lastKey();
						int lastValue = map.get(lastKey);
						if (lastValue == 1) {
							map.remove(lastKey);
						} else {
							map.put(lastKey, lastValue - 1);
						}
					}
				}

			}
			if (map.size() == 0)
				System.out.println("EMPTY");
			else
				System.out.println(map.lastKey() + " " + map.firstKey());
		}
	}
}