[Java][프로그래머스] 42628번, 이중우선순위큐

프로그래머스

 

42628, 이중우선순위큐

🔥 난이도 : LEVEL 3

 

📁 프로세스

문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어 수신 탑(높이)
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항
operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다.
원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
입출력 예
operations return
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"] [0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] [333, -45]
입출력 예 설명
입출력 예 #1

16과 -5643을 삽입합니다.
최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
123을 삽입합니다.
최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.
따라서 [0, 0]을 반환합니다.

입출력 예 #2

-45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다.
-642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다.
333을 삽입합니다.
이중 우선순위 큐에 -45, 45, 333이 남아있으므로, [333, -45]를 반환합니다.

 

🔽 문제풀이

문제에서 알려주다 싶이, 이중우선순위 큐를 사용해서 문제를 풀이했다. 오름차순과 내림차순으로 정렬되는 우선순위 큐 2개를 초기화한다.

// 오름차순, 작은 수부터 poll
PriorityQueue<Integer> minQ = new PriorityQueue<>(); 
// 내림차순, 큰 수부터 poll
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());

 

오름차순으로 정렬된 minQ 를 poll할 경우는 작은 수부터, maxQ는 큰 수부터 poll() 이 되는 성질을 사용했다.

차례대로 operations 를 문자와 수로 분리.

 

1. 문자가 "I" 인 경우

minQ, maxQ 각각에 수를 입력한다.

 

2. 그 외의 경우

큐가 비어있지 않은 경우, 최대/최소 값을 poll하고, 그 반대에서 삭제해주면 된다. 두 큐 동시에 삽입/삭제를 진행하기 때문에 maxQ를 기준으로 Empty 여부를 판별했다.

여기서 신기한 점은 PriorityQueue 의 remove는 Object 를 파라미터로 받고 그 값 자체를 삭제할 수 있는 기능을 지원한다. 이를 통해 poll 한 값의 객체를 넣어 삭제를 진행했다.

PriorityQueue.class

/**
 * Removes a single instance of the specified element from this queue,
 * if it is present.  More formally, removes an element {@code e} such
 * that {@code o.equals(e)}, if this queue contains one or more such
 * elements.  Returns {@code true} if and only if this queue contained
 * the specified element (or equivalently, if this queue changed as a
 * result of the call).
 *
 
 * @param o element to be removed from this queue, if present
 * @return {@code true} if this queue changed as a result of the call
 */
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

for(String o : operations) {
    st = new StringTokenizer(o, " ");
    type = st.nextToken();
    N = Integer.parseInt(st.nextToken());

    if(type.equals("I")) {
        minQ.add(N);
        maxQ.add(N);
    }
    else {
        if(!maxQ.isEmpty()) {
            // 최대값 삭제
            if(N == 1) {
                int max = maxQ.poll();
                minQ.remove(max);
            }
            // 최솟값 삭제
            else {
                int min = minQ.poll();
                maxQ.remove(min);
            }  
        }
    }
}

 

✅ 전체코드

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

public class Solution {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
   

    public static void main(String[] args) {
        // String[] operations = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};
        String[] operations = {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};

        int[] answer = solution(operations);
        System.out.println(answer[0] + ":" + answer[1]);
    }

    public static int[] solution(String[] operations) {
        int[] answer = new int[2];
        // 오름차순, 작은 수부터 poll
        PriorityQueue<Integer> minQ = new PriorityQueue<>(); 
        // 내림차순, 큰 수부터 poll
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder()); 
        
        StringTokenizer st;
        String type;
        int N;

        for(String o : operations) {
            
            st = new StringTokenizer(o, " ");
            type = st.nextToken();
            N = Integer.parseInt(st.nextToken());

            if(type.equals("I")) {
                minQ.add(N);
                maxQ.add(N);
            }
            else {
                if(!maxQ.isEmpty()) {
                    // 최대값 삭제
                    if(N == 1) {
                        int max = maxQ.poll();
                        minQ.remove(max);
                    }
                    // 최솟값 삭제
                    else {
                        int min = minQ.poll();
                        maxQ.remove(min);
                    }  
                }
            }
        }
        
        if(maxQ.isEmpty()) 
           return new int[]{0,0};
         
        return new int[]{maxQ.poll(),minQ.poll()};
    }
}