[프로그래머스] 이중우선순위큐 [JAVA(자바)]

‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀

문제 👉 <코딩테스트 연습 - 이중우선순위큐 | 프로그래머스>

1. 문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 의미한다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 한다.

빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시한다.

2. 풀이

PriorityQueue 를 이용한 문제 풀이

• 최대값을 위한 최대힙을 이용하여 PriorityQueue 로 나타낸다.
• 최소값을 위한 최소힙을 이용하여 PriorityQueue 로 나타낸다.

1. 삽입은 최대힙과 최소힙 모두에 한다.
2. 최대값을 삭제할 때는 최대힙에서 poll() 을 사용하고, 최소힙에서 remove() 함수로 삭제한다.
3. 최소값을 삭제할 때는 최소힙에서 poll() 을 사용하고, 최대힙에서 remove() 함수로 삭제한다.

3. 코드

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // 연산
        for (String op : operations) {
            // 삽입
            if (op.substring(0,1).equals("I")) {
                int value = Integer.valueOf(op.substring(2));     
                minHeap.offer(value);
                maxHeap.offer(value);          
            }          
            // 값이 있을 때
            else if (!minHeap.isEmpty()) {
                // 최대값 삭제
                if (op.equals("D 1")) {
                    int value = maxHeap.poll();
                    minHeap.remove(value);
                }
                // 최소값 삭제
                else if (op.equals("D -1")) {
                    int value = minHeap.poll();
                    maxHeap.remove(value);       
                }
            }            
        }

        // 값이 있을 때
        if (!minHeap.isEmpty()) {
            answer[0] = maxHeap.peek();
            answer[1] = minHeap.peek();
        }

        return answer;
    }
}   

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋