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

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

프로그래머스

 

1. 서론

 

level 3문제답게 쉽지가 않다. 특히나 우선순위 큐를 사용해야 해서 더욱. 

 

2. 문제 풀이

 

세 종류의 명령이 있다. I 숫자, D 1, D -1이라는 명령 있고 순서대로 첫 번째는 I 뒤의 숫자를 입력하고, D 1이 명령으로 들어오면 최댓값을, -1이 들어오면 최솟값을 삭제한다. 여러 명령이 주어졌을 때 이 규칙에 따라 명령을 수행한다면 나올 수 있는 최댓값과 최솟값을 배열 형태로 return 하는 게 이번 문제다.

 

우선순위 큐 한 개만 가지고 풀려다가 중간에 한 번씩 정렬 기준 바꾸면 되려나? 했는데 우선순위 큐는 그렇게 중간에 정렬 기준을 바꿀 수 없고 정의한대로만 정렬이 가능하며, 값을 넣는 순간 자동으로 정렬해준다. 그렇기 때문에 그러면 어떻게 최대, 최솟값을 큐에서 꺼낼 수가 있단 말이지? 해결법이 떠오르지 않아 바로 인터넷을 뒤졌다.

 

https://lkhlkh23.tistory.com/115

[프로그래머스, 자바] 이중우선순위 큐 - 힙

 

의외로 아이디어 자체는 간단했다. 큐를 두 개 사용 하는 것이다. (최소용 최대용)

그리고 나중에 알았는데 우선순위 큐에 remove(값)을 사용하면 해당하는 값을 큐에서 제거할 수 있다고 한다.

(최고다. 알아서 기준대로 정렬을 다해주고, 큐인데도 중간값을 삭제할 수 있다니.)

 

그래서 내림차순, 오름차순 하는 정렬 값을 가진 각각의 큐에 입력값을 넣어주고,

만약 최댓값을 제거해야 한다면 최댓값 큐에서 첫 번째 값을 빼주고 최솟값 큐에서 그 첫 번째 값을 찾아서 지워준다.

그리고 명령을 따라 이를 반복하면 답을 구할 수 있다.

 

3. 코드 설명

 

import java.util. *;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        
        Queue<Integer> qmin = new PriorityQueue<>();
        Queue<Integer> qmax = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < operations.length; i++) {
            if(operations[i].charAt(0) == 'I') {
                qmin.add(Integer.parseInt(operations[i].substring(2)));
                qmax.add(Integer.parseInt(operations[i].substring(2)));
            }
            else if (operations[i].equals("D 1")) {
                if (!qmin.isEmpty())
                    qmin.remove(qmax.poll());
            }
            else {
                if (!qmax.isEmpty())
                    qmax.remove(qmin.poll());
            }
        }
        
        if (qmax.isEmpty()) {
            answer[0] = 0;
            answer[1] = 0;
        }
        else {
            answer[0] = qmax.poll();
            answer[1] = qmin.poll();
        }
        
        return answer;
    }
}

 

String 값들을 다 int로 전환해서 명령을 처리해줬다. 그리고 remove 할 때 큐가 비어 nullPointException이 날 수도 있기 때문에 꼭 예외처리를 해야 한다.

 

pq.remove(value); 가 가능하단 걸 알게 된 좋은 문제^^