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

문제링크 🚩

https://school.programmers.co.kr/learn/courses/30/lessons/42628?language=java 

프로그래머스

​

📕 문제 접근 📕

1. 문제에서 최대값과 최소값을 뽑는 문제라면 우선순위 큐를 사용하고 Deque를 사용하면 되지 않을까???

자바의 Deque는 우선순위를 직접 지원하지 않는다.

2. 우선순위 큐를 2개를 작성하여 해결하자

• 오름차순 큐와 내림차순 큐를 2개 만들고 각 값을 넣어야할 때 두가지 큐에 전부 push를 해준다.
• 만약 최대값을 뽑아야한다면 최대 큐에서 poll을 하고 해당 값을 최소 큐에서 삭제한다.
• 먄약 최소값을 뽑아야한다면 최소 큐에서 poll을 하고 해당 값을 최대 큐에서 삭제한다.
• 모든 연산이 끝난 뒤 마지막으로 최대큐와 최소 큐에서 한 번씩 poll을 하여 결과 값을 반환한다.

💻 Code 💻

import java.util.*;

public class Solution {
    private PriorityQueue<Integer> max;
    private PriorityQueue<Integer> min;

    public int[] solution(String[] operations) {
        min = new PriorityQueue<>();
        max = new PriorityQueue<>(Collections.reverseOrder());

        for (String operation : operations) {
            String[] tokens = operation.split(" ");
            char command = tokens[0].charAt(0);
            int num = Integer.parseInt(tokens[1]);

            if (command == 'I') {
                push(num);
            } else if (command == 'D') {
                if (num == 1) {
                    maxPop();
                } else if(num == -1) {
                    minPop();
                }
            }
        }

        int[] answer = new int[2];
        if (!max.isEmpty()) {
            answer[0] = max.poll();
            answer[1] = min.poll();
        }

        return answer;
    }

    public void push(int num) {
        max.add(num);
        min.add(num);
    }

    public void maxPop() {
        if (!max.isEmpty()) {
            int num = max.poll();

            min.remove(num);
        }
    }

    public void minPop() {
        if (!min.isEmpty()) {
            int num = min.poll();

            max.remove(num);
        }
    }
}

💻 Code Review**💻**

• 변수명에서의 아쉬운 점 : maxHeap,minHeap과 같은 보다 직관적인 명시가 가능했을 것 같다
• 가독성 측면에서의 아쉬운점 : if문 대신 switch문을 사용한다면 보다 가독성이 높았을 것 같다

  switch (command) {
                case 'I':
                    push(num);
                    break;
                case 'D':
                    if (num == 1) {
                        popMax();
                    } else if (num == -1) {
                        popMin();
                    }
                    break;
                default:
                    break;

📖 배운점 및 느낀점 📖

• 처음에 문제를 보고 데큐와 우선순위큐를 떠올렸지만 아쉽게도 자바 데큐에서는 지원하지 않는다는 점을 알게 되었으며 이중 우선순위 큐 문제를 처음 접해봤는데 2가지 큐를 함께 사용하면서 서로의 값을 삭제해주는 연산을 생각해내는 것이 어려웠다.