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

문제 링크

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

코딩테스트 연습 - 이중우선순위큐

 

우선순위 큐 자료구조에서 최소와 최대를 한번에 관리하도록 요구하는 문제.

우선순위 큐
일반적인 큐의 구조에서, 선입 선출이 아닌 내가 정해둔 우선 순위가 먼저 나가도록 하는 자료구조이다.
주로 힙으로 구성된다 (이진트리)
최대 값이 우선순위 : 최대 힙 최소 값이 우선순위 : 최소 힙

 

명령어	내용
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

 

최소 힙, 최대 힙을 각각 하나씩 만들어 마치 하나의 큐처럼 다룰 수 있도록 설계하였다.

또한 size변수를 만들어 '실제 큐의 크기'를 설정해두었다.

 

실제 큐의 크기? 무슨소릴까
ex) 1 2 3 4가 삽입될 경우
D1 D1 D -1 D -1의 경우, 최대값 두 개 최솟값 두 개를 삭제하면서 큐가 비어야 하지만
최소 힙 : 3 4  최대 힙 : 1 2가 남아있게 된다.
따라서 size == 0일 경우 각 힙을 모두 비워주어야 함

 

• 숫자를 삽입할 경우 두 큐에 모두 값을 넣는다 size++;
• 최댓값을 삭제할 경우 최대 큐의 원소를 삭제한다. size--;
• 최솟값을 삭제할 경우 최소 큐의 원소를 삭제한다. size--;
• size == 0일 경우 각 큐의 원소를 모두 지워준다

import java.util.PriorityQueue;
import java.util.Collections;
class Solution {
    public void erase(PriorityQueue<Integer> num, PriorityQueue<Integer> num2, int size) {
        num.poll();
        if (size == 0) {
            while (num.size() != 0)
                num.poll();
            while (num2.size() != 0)
                num2.poll();
        }
    }
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder()); 
        PriorityQueue<Integer> min = new PriorityQueue<>();
        int size = 0;
        
        for (int i = 0; i < operations.length; i++) {
            if (operations[i].contains("I")) {
                size++;
                max.add(Integer.parseInt(operations[i].substring(2)));
                min.add(Integer.parseInt(operations[i].substring(2)));
            }
            else if (operations[i].contains("-") && min.size() != 0) {
                size--;
                erase(min, max, size);
            }
            else {
                if (max.size() != 0)
                    size--;
                erase(max, min, size);
            }
        }
        if (size >= 2) {
            answer[0] = max.peek();
            answer[1] = min.peek();
        }
        return answer;
    }
}