[프로그래머스/자바] 이중우선순위큐 풀이

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

프로그래머스

 

프로그래머스 코딩테스트 고득점 Kit의 힙 Level 3 문제다.

 

 

문제 제목 그대로 우선순위 큐를 두개 사용하면 되는 간단한 문제다.

최소 힙과 최대 힙 둘다 생성하고, I 연산을 통해 값을 삽입할 때도 두개의 힙에 삽입한다.

 

그러면 자동으로 최소 힙에서 poll을 하면 최솟값이 삭제되고,

최대 힙에서 poll을 하면 최대값이 삭제될 것이다.

 

그리고 최솟값을 삭제할시 최대 힙에서도 동일한 값을 삭제하고,

최댓값을 삭제할시 최소 힙에서도 동일한 값을 삭제해야 한다.

이를 구현하기 위해 poll한 값을 저장해 remove() 메소드에 전달했다.

 

처음엔 우선순위 큐의 remove() 메소드가 인덱스를 통해 접근하는 줄 알고 헤맸는데,

값을 통해 원소를 삭제하는 메소드라 더 간단하게 구현할 수 있었다.

 

<최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.>

라는 조건이 있기 때문에 remove(value)를 한번 해주면 된다.

 

 

import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.Collections;
import java.util.Iterator;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        StringTokenizer st;
        
        for(int i=0;i<operations.length;i++) {
            st = new StringTokenizer(operations[i]);
            char op = st.nextToken().charAt(0);
            int num = Integer.parseInt(st.nextToken());
            
            switch(op) {
                case 'I':
                    min.add(num);
                    max.add(num);
                    break;
                case 'D':
                    if(max.isEmpty()) break;
                    if(num == 1) {
                        int del = max.poll();
                        min.remove(del);
                    }
                    if(num == -1) {
                        int del = min.poll();
                        max.remove(del);
                    }
            }
        }
        
        if(max.isEmpty())
            return new int[] {0, 0};
        
        return new int[] {max.peek(), min.peek()};
    }
}