[programmers] 이중우선순위큐 (Java)

[이중우선순위큐]

[코딩테스트 연습 > 힙(Heap) > 이중우선순위큐]

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

프로그래머스

 

[접근방법]

이중우선순위 큐 문제는 2개의 큐를 생성해야한다.

오름차순으로 정렬된 큐 / 내림차순으로 정렬된 큐 이 2가지를 가지고 해결을 진행한다.

 

'숫자 삽입' , '최솟값 삭제' , '최댓값 삭제' 등의 기능을 수행할때, 두개의 큐가 동기화 되어서 실행되어야 한다.

 

[Java 코드]

//https://school.programmers.co.kr/learn/courses/30/lessons/42628
//코딩테스트 연습 - 힙(Heap) - 이중우선순위큐

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (String operation : operations) {
            String[] parts = operation.split(" ");
            String command = parts[0];
            int number = Integer.parseInt(parts[1]);

            //숫자 삽입
            if (command.equals("I")) {
                minHeap.add(number);
                maxHeap.add(number);
            } 
            //숫자 삭제
            else if (command.equals("D")) {
                //최댓값 삭제
                if (number == 1) {
                    if (!maxHeap.isEmpty()) {
                        int maxValue = maxHeap.poll();
                        minHeap.remove(maxValue);
                    }
                }
                //최솟값 삭제
                else if (number == -1) {
                    if (!minHeap.isEmpty()) {
                        int minValue = minHeap.poll();
                        maxHeap.remove(minValue);
                    }
                }
            }
        }

        if (!minHeap.isEmpty() && !maxHeap.isEmpty()) {
            return new int[] {maxHeap.peek(), minHeap.peek()};
        }
        
        return new int[] {0, 0};
    }
}

 

[Rewind]

1. 어려웠던 점

- 우선순위 큐에 대해 잘 알지 못해 접근에 어려움을 느낀다.

 

2. 알게된 점

- "heap.remove(data)" data 를 통해, 데이터를 선별적으로 삭제할 수 있다.

 

3. 개선방안