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

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

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

 

풀이

최댓값과 최솟값의 삭제를 모두 고려해야하는 문제입니다.

사실 큐 하나로 최솟값 삭제와 최댓값 삭제를 모두 구현하는게 정석일 것 같지만 코테는 빠른시간안에 코드를 구현해야하니까...

저는 그냥 우선순위 큐 2개를 사용해서 문제를 풀었습니다.

 

1. 우선 순위큐를 2개 선언합니다. 하나는 최댓값이 맨위에 오는 우선순위 큐(pq1) / 다른 하나는 최솟값이 맨위에 오는 우선순위 큐(pq2)
2. 삭제와 삽입을 반복하면서 큐에 몇개의 수가 남게 되는지 확인하는 변수 cnt 사용
3. 그런 뒤 operations를 하나씩 읽어오면서 해당하는 연산을 수행합니다.
   1. 'I'의 경우엔 우선순위 큐에 삽입하고 cnt++
   2. 'D'의 경우엔 cnt가 0이상인 경우만 최댓값 삭제의 경우 pq1에서 remove(), 최솟값 삭제의 경우 pq2에서 remove()
   3. 삭제 연산 후엔 cnt-- 후 cnt가 0이 된 경우 두 우선순위 큐를 모두 clear해줍니다.
4. 모든 operations에 대해 완료 후
   1. cnt == 1인 경우, 최댓값과 최솟값이 같습니다. (pq2.peek()또는 -pq1.peek())
   2. cnt > 1인 경우, 최댓값 = -pq1.peek(), 최솟값 = pq2.peek()

 

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        int cnt = 0;
        PriorityQueue<Integer> pq1 = new PriorityQueue<>(); //큰 값이 top
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(); //작은 값이 top
        
        for(String data : operations){
            if(data.charAt(0) == 'I'){
                cnt++;
                String num = data.substring(2);
                int n = Integer.parseInt(num);
                pq1.add(-n);
                pq2.add(n);
            }
            else if(data.charAt(0) == 'D'){
                if(cnt == 0)
                    continue;
                
                //최솟값 삭제
                if(data.charAt(2) == '-'){
                    pq2.remove();
                }
                //최댓값 삭제
                else{
                    pq1.remove();
                }
                cnt--;
                if(cnt == 0){
                    pq1.clear();
                    pq2.clear();
                }
            }
        }
        if(cnt == 1){
            answer[0] = pq2.peek();
            answer[1] = answer[1];
        }
        else if(cnt > 1){
            answer[0] = -pq1.peek();
            answer[1] = pq2.peek();
        }
        return answer;
    }
}