[프로그래머스] 이중우선순위큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

이 문제는 문자열 배열이 들어오는데, 문자열의 첫 시작이 (I 숫자) 라면 큐에 숫자를 삽입하고,

(D 1)이 들어오면 제일 큰 수를 삭제한다. (D -1) 일 경우 가장 작은 수를 삭제해야 한다.

 

핵심

큐에서 삭제순서를 정할 수 있지만, 중간에 바꿀 수는 없다.

따라서 우선순위 큐를 2개를 선언하여 사용하면 쉽게 풀 수 있다.

 

정답 코드

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minQ = new PriorityQueue<>();
        int[] answer = {0, 0};

        for (String operation : operations) {
            String condition = operation.split(" ")[0];
            Integer value = Integer.parseInt(operation.split(" ")[1]);
            if (condition.equals("I")){
                minQ.add(value);
                maxQ.add(value);
                continue;
            }
            if (maxQ.isEmpty()||minQ.isEmpty())continue;
            if (value==1){
                int delete = maxQ.poll();
                minQ.remove(delete);
            }else {
                int delete = minQ.poll();
                maxQ.remove(delete);
            }
        }
        if (!maxQ.isEmpty()){
            answer[0] = maxQ.poll();
            answer[1] = minQ.poll();
        }
        return answer;
    }
}

해설

앞서 말한 대로 우선큐를 2개를 선언한다. 한 개는 큰 수부터 제거하는 우선 큐와 다른 한 개는 작은 수부터 제거하는 우선 큐이다.

문제의 규칙대로 I로 시작하면 숫자를 각각 넣어준다.

이후 큰 수를 삭제하라는 명령이 오면, maxQ에서 제거한 뒤, 제거한 요소를 minQ에서도 삭제해 준다.

반대로 작은 수는 minQ에서 제거 후 제거된 요소를 maxQ에서 삭제해 준다.

만약 큐가 비어있는 상태에서 제거 요청이 오면 무시된다.

 

 

배운 점

기존에 우선 큐의 존재를 알았고, 반대로 최대 값 우선순위 형태로 만드는 Collections.reverseOrder()를 기존에 알아서 쉽게 풀 수 있었다. 만약 기존에 이러한 사전 지식이 없다면, 푸는 것이 결코 쉽지는 않을 것이다.

힙 문제도 생각보다 중요하다고 생각한다.

이러한 스킬을 익혀두는 것이 좋을 것 같다.