백준 7662 이중 우선순위 큐

문제 바로가기

문제

이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.

정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.

Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최댓값과 최솟값을 출력하는 프로그램을 작성하라.

I 16
I -5643
D -1
D 1
D 1

요런 식으로 Input이 들어오는데,
I는 큐에 값을 넣을 때고,
D는 1일 때는 큐에서 최댓값을 삭제, -1은 최솟값 삭제다.

접근 방식

1. 우선순위큐를 두 개 써서 하면 되지 않을까?
   하나는 오름차순 하나는 내림차순을 생각해봤으나 큐 복사가 자주 일어나기 때문에 오버헤드가 크므로 재빠르게 포기했다.

2. Tree Map을 써보자!
   조건에 동일한 정수가 삽입 될 수 있다고 했는데, 같은 key가 들어오면 value값에 +1을 해주면 충분히 해결할 수 있다고 판단하였다.
   다만 삭제 할 때는 value가 1일때만 해당 key가 트리맵에서 사라지도록 조건을 넣어줘야한다.

위 두 개만 처리해주면 된드아!!

코드

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

public class Main_7662 {

    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());
        for (int i = 0; i < T; i++) {
            //트리맵 선언
            TreeMap<Integer, Integer> tm = new TreeMap<>();
            int k = Integer.parseInt(br.readLine());
            for (int j = 0; j < k; j++) {
                String[] x = br.readLine().split(" ");
                int v = Integer.parseInt(x[1]);
                if (x[0].equals("I")) {
                    //트리맵에 v가 key로 있다면 해당 key의 value값과 1을 sum하고
                    //트리맵에 v가 없다면 1을 value로 넣어준다
                    tm.merge(v, 1, Integer::sum);
                } else {
                    //트리맵이 비었다면 그냥 무시
                    if (tm.isEmpty()) continue;
                    
                    int key = (v == 1) ? tm.lastKey() : tm.firstKey();
                    //value가 1보다 크면 -1을 해주고 1이라면 key를 트리맵에서 없애둔다
                    if(tm.get(key) > 1) tm.put(key,tm.get(key) - 1);
                    else tm.remove(key);
                }
            }
            if (tm.isEmpty()) sb.append("EMPTY");
            else sb.append(tm.lastKey()).append(" ").append(tm.firstKey());
            sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

Discussion

merge 라는 메소드를 처음 사용해봤다.

코드를 보면 파라미터로 key, value, function을 받는데,
맵에 해당 key가 없으면 value값을 넣어주고
맵에 key가 있다면 맵에있는 oldvalue와 파라미터의 value를 function의 인자로 넘겨주고
결과값이 null이라면 맵에서 key를 지우고 null이아니라면 새로 맵에 매핑 해준다.

그리고

function은 람다 꼴 인걸 알수 있는데,

	(x1, x2) -> Integer.sum(x1,x2);

양쪽에 파라미터가 중복해서 쓰이므로

	Integer::sum

줄여셔 이렇게 쓸 수 있다고 한다.
메소드 참조 표현식이라고 한다.