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

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

문제

---

풀이

자바의 TreeMap을 사용하면 쉽게 해결할 수 있다

TreeMap에 객체를 저장하면 자동으로 오름차순으로 정렬된다

`key`: 입력한 정수 / `value`: 입력한 정수가 몇개 있는지

 

n을 map에 넣어줄 때 이미 map에 n이 있다면 기존 n의 value에 1을 더해준다 (이제 n이 2개 있다는 뜻)

제거할 때는 최댓값, 최솟값을 뽑아준 후, map에 해당 키가 하나만 존재한다면 map에서 제거하고 아니라면 value 값을 -1 해준다

 

자세한 것은 코드를 보자

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {


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


		// D 1 -> 최댓값 제거
		// D -1 -> 최솟값 제거
		int T = Integer.parseInt(br.readLine());
		while (T-- > 0) {
			// 키: 입력한 정수, 값: 입력한 정수가 몇개 있는지
			TreeMap<Long, Integer> map = new TreeMap<>();
			int k = Integer.parseInt(br.readLine());
			for (int i = 0; i < k; i++) {
				st = new StringTokenizer(br.readLine());
				String cmd = st.nextToken();
				long n = Long.parseLong(st.nextToken());

				if (cmd.equals("I")) {
					// n을 키에 넣고, n이 없다면 값을 1로 하고
					// n이 중복으로 들어왔다면 기존 n의 value에 1을 더해줌
					map.put(n, map.getOrDefault(n, 0) + 1);
				} else {
					if(map.isEmpty()) continue; // map이 비어있다면 continue
					if (n == 1) {
						long max = map.lastKey(); // map에서 최댓값을 뽑아온다
						// 뽑아온 값이 map에 하나만 있다면 map에서 제거한다
						if(map.get(max) == 1) map.remove(max);
						// 여러개 있다면 value를 -1 해준다
						else map.put(max, map.get(max) - 1);
					} else {
						long min = map.firstKey(); // map에서 최솟값을 뽑아온다
						// 뽑아온 값이 map에 하나만 있다면 map에서 제거한다
						if(map.get(min) == 1) map.remove(min);
						// 여러개 있다면 value를 -1 해준다
						else map.put(min, map.get(min) - 1);
					}
				}
			}
			// map이 비어있다면 EMPTY 출력
			if (map.isEmpty()) {
				sb.append("EMPTY\n");
			} else {
				// 비어있지 않다면 최댓값과 최솟값 출력
				sb.append(map.lastKey() + " " + map.firstKey()).append("\n");
			}
		}

		System.out.println(sb);

		br.close();
	}
}

결과