[프로그래머스] 이중우선순위큐 Java 풀이 및 해설

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

프로그래머스

 

풀이 방법

1. 최대힙과 최소힙 두개의 힙을 사용합니다.
2. 삽입 연산시 두 힙에 모두 삽입합니다.
3. 최대/최소값 삭제 연산시 해당 힙에서 삭제를합니다.
4. 그럼 해당 힙이 아닌 다른 힙에서의 데이터 불일치는 어떻게 해결하나?
5. Map을 통해 값의 삽입, 삭제 기록을 남깁니다. 즉, 남은 값의 개수를 Map의 Value로 사용합니다.
6. 힙에서 삭제 연산시 Map에서 남은 값이 존재하는지 확인 후에 존재하면 삭제연산을 정상적으로 합니다.
7. 남은 값이 존재하지 않으면 삭제 연산은 하지 않습니다.
8. getExistKey : 힙을 돌며 남은 값이 존재하는 키를 반환합니다. 

 

전체 코드

import java.util.*;
class Solution {
    
    // 삭제되지 않고 남아 있는 값을 찾는 메서드
    public Integer getExistKey(Map<Integer, Integer> m, PriorityQueue<Integer> pq) {
        while(true) {
            Integer key = pq.poll();
            Integer value = m.getOrDefault(key, 0);
            
            // 뽑을 키가 없으면
            if(key == null)
                return null;
            
            // 
            if(value>0)
                return key;
        }
    }
    
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        
        // 최소, 최대 힙 선언
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        // 값이 남아 존재하는지 확인하는 Map
        Map<Integer, Integer> m = new HashMap<>();
        
        // 배열 operations에서 i번쨰 원소는 get(i)가 아닌 [i]임.
        for(int i=0; i<operations.length; i++) {
            String[] str = operations[i].split(" ");
            if(str[0].equals("I")) {
                
                // Integer.parseInt(), Integer.valueOf()
                Integer value = Integer.valueOf(str[1]);
                
                minHeap.add(value);
                maxHeap.add(value);
                if(m.get(value) == null)
                    m.put(value, 1);
                else
                    m.put(value, m.get(value) + 1);   
            } else {

                if(str[1].equals("-1")) {
                    Integer key = getExistKey(m, minHeap);
                    Integer value = m.getOrDefault(key, 0);
                    if(key!=null && value>0) {
                        m.put(key, value-1);
                    }
                } else {
                    Integer key = getExistKey(m, maxHeap);
                    Integer value = m.getOrDefault(key, 0);
                    if(key!=null && value>0) {
                        m.put(key, value-1);
                    }
                }
            }
        }
        
        Integer maxKey = getExistKey(m, maxHeap);
        Integer maxValue = m.getOrDefault(maxKey, 0);
        if(maxKey!=null && maxValue>0)
            answer[0] = maxKey;
        else
            answer[0] = 0;
        
        Integer minKey = getExistKey(m, minHeap);
        Integer minValue = m.getOrDefault(minKey, 0);
        if(minKey!=null && minValue>0)
            answer[1] = minKey;
        else
            answer[1] = 0;
        
        return answer;
    }
}