BEAKJOON / 백준 - JAVA 7662번 이중 우선순위 큐

2024.08.15기준 - 골드4

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 주어진 키워드가 I 또는 D가 들어올 때, I n 이면 n을 추가 D 1 이면 최댓값을 D -1이면 최솟값을 제거 후 최댓값과 최솟값을 출력하는 문제입니다.

 

이 문제는 시간초과가 많이 나와 여러가지 방법을 찾다가 TreeMap을 활용하여 문제에 접근하게 되었습니다.

처음엔 priorityqueue를 이용해 오름차순, 내림차순의 큐를 2개 생성해 해당 값을 제거할 때, remove를 사용해 제거를 진행했지만 시간초과가 나와 여러가지 방법을 생각해보았습니다.

 

우선 TreeMap에 대한 설명을 하자면

1. 키의 자동 정렬
   • TreeMap은 키를 기준으로 자동으로 정렬을 합니다.
   • 기본적으로 오름차순으로 정렬되지만, 커스텀 Comparator를 사용하면 정렬 방식을 변경할 수 있습니다.
2. 레드 - 블랙 트리 기빈
   • 내부적으로 레드-블랙 트리 구조를 사용하여 효울적인 검색, 삽입, 삭제 연산을 제공해줍니다.

 

1. TreeMap을 생성 후 키워드에 I가 들어온다면 switch문을 통해 map에 값을 추가 시켜줍니다.

(map.getOrDefault() 메서드를 활용해 값이 있다면 해당 값을 없다면 0을 기반으로 +1을 해줍니다.)

case "I": // 수를 map에다가 저장
    map.put(num, map.getOrDefault(num, 0) + 1);
    break;

 

2. 키워드에 D가 들어온다면 1 과 -1를 참조해 최솟값 또는 최댓값을 제거해주도록 합니다.

TreeMap에는 lastKey()와 firstKey()메서드가 존재합니다. 그래서 최댓값과 최솟값의 수를 한 번에 찾을 수 있습니다.

key = num == 1 ? map.lastKey() : map.firstKey();

 

그래서 map이 비어있지 않다면 값을 제거하는 데, 그 개수가 0이 된다면 map에서 제거를 해줍니다.

case "D": // 최솟값 or 최댓값 제거
    if (!map.isEmpty()) { // map에 값이 있다면
        // num 이 1이면 최댓값을 -1이면 최솟값의 key를 저장.
        key = num == 1 ? map.lastKey() : map.firstKey();

        // map.put()은 값이 변환되기 이전에 값을 반환하기 때문에 참조하는 key의 개수가 1이라면 제거를 해줍니다.
        if (map.put(key, map.get(key) - 1) == 1) {
            map.remove(key);
        }
    }
    break;

 

3. 이렇게 정리된 map을 통해 비어있다면 "EMPTY"를 출력 아니라면 최댓값과 최솟값을 출력합니다.

if (map.isEmpty()) { // map이 비어있다면
    sb.append("EMPTY\n");
} else { // map에 값이 있다면
    sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
}

 

 

코드

package Main;

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int t = Integer.parseInt(br.readLine());
		
		String s;
		int n, num, key;
		StringTokenizer st;
		TreeMap<Integer, Integer> map; // 들어오는 수를 담을 treemap
		
		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());
			map = new TreeMap<>();
			
			while (n-- > 0) {
				st = new StringTokenizer(br.readLine());
				s = st.nextToken();
				num = Integer.parseInt(st.nextToken());
				
				switch (s) {
				case "I": // 수를 map에다가 저장
					map.put(num, map.getOrDefault(num, 0) + 1);
					break;
				case "D": // 최솟값 or 최댓값 제거
					if (!map.isEmpty()) { // map에 값이 있다면
						// num 이 1이면 최댓값을 -1이면 최솟값의 key를 저장.
						key = num == 1 ? map.lastKey() : map.firstKey();
						
						// map.put()은 값이 변환되기 이전에 값을 반환하기 때문에 참조하는 key의 개수가 1이라면 제거를 해줍니다.
						if (map.put(key, map.get(key) - 1) == 1) {
							map.remove(key);
						}
					}
					break;
				}
			}
			
			if (map.isEmpty()) { // map이 비어있다면
				sb.append("EMPTY\n");
			} else { // map에 값이 있다면
				sb.append(map.lastKey()).append(" ").append(map.firstKey()).append("\n");
			}
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}