[프로그래머스 알고리즘 고득점 Kit][힙(Heap)][Java] 이중우선순위큐

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

프로그래머스

 

 

문제이름이 너무 힌트라 2개의 우선순위큐를 사용하는 방법을 생각했다.

최댓값과 최솟값을 항상 관리해야 하는데

하나의 우선순위큐로는 쉽지 않다.

그래서 최대를 관리하는 우선순위큐와 최소를 관리하는 우선순위큐를 나눠서 관리한다.

그러면 여기서 하나의 수열에서 최대와 최소를 관리해야 하는데 2개로 나눴기 때문에

다른 하나의 우선순위큐에서 삭제 혹은 추가는 다른 우선순위큐에서도 적용이 되어야 한다.

추가는 둘 다 추가하면 된다.

삭제는 바로 꺼내서 삭제할 수 없기 때문에

하나의 우선순위 큐에서 삭제하면 그 수는 다른 우선순위에서 꺼내질 때 과거에 삭제된 숫자

임을 보여주기 위해 클래스로 isActive를 만들어서 추가해 줬다.

그러고 나서 모든 커맨드를 끝내고

최대와 최소를 꺼낼때도 그 숫자가 과거에 삭제된 숫자임을 확인해줘야한다.

 

import java.util.*;

class Solution {
    
    class Num {
        int num;
        boolean isActive;
        
        Num(int num) {
           this.num = num;
            this.isActive = true;
        }
        void disable() {
            this.isActive = false;
        }
    }
    
    public int[] solution(String[] operations) {
        PriorityQueue<Num> minPq = new PriorityQueue<>((n1, n2) -> {
            return Integer.compare(n1.num, n2.num);
        });
        PriorityQueue<Num> maxPq = new PriorityQueue<>((n1, n2) -> {
            return Integer.compare(n2.num, n1.num);
        });
        
        
        for(String s : operations) {
            StringTokenizer st = new StringTokenizer(s);
            char cmd = st.nextToken().charAt(0);
            int num = Integer.parseInt(st.nextToken());
            
            if(cmd == 'I') {
                Num n = new Num(num);
                minPq.add(n);
                maxPq.add(n);
            } else {
                if(num == 1) {
                    while(!maxPq.isEmpty()) {
                        Num n = maxPq.poll();
                        if(n.isActive) {
                            n.disable();
                            break;
                        }
                    }
                    
                    
                } else if(num == -1) {
                    while(!minPq.isEmpty()) {
                        Num n = minPq.poll();
                        if(n.isActive) {
                            n.disable();
                            break;
                        }
                    }
                }
            }
        }
        int max = 0;
        int min = 0;
        while(!maxPq.isEmpty()) {
            Num n = maxPq.poll();
            if(n.isActive) {
                max = n.num;
                break;
            }
        }
        while(!minPq.isEmpty()) {
            Num n = minPq.poll();
            if(n.isActive) {
                min = n.num;
                break;
            }
        }
        int[] answer = {max, min};
        
        return answer;
    }
}