LV3 이중우선순위큐

 

---

 

문제

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

프로그래머스

 

풀이

 

대놓고 문제에 우선순위큐가 적혀있는만큼, 우선순위큐를 이용하여 풀 수 있다.

 

해당 문제는 최댓값이나 최솟값을 효율적으로 구해야한다. 따라서 우선순위큐를 사용하되, 최대힙과 최소힙 두개를 선언한다.

 

우선 값을 넣을땐 두 큐에 모두 넣어준다.

 

이후에 D -1 가 나오면 최소힙에서 값을 빼주면 되고,

D 1이 나오면 최대힙에서 빼주면 된다.

 

여기서 발생하는 문제는, 최소힙에서 뺀 값을 최대힙에서도 제거를 해주어야 한다는 점이다. 한마디로 요소의 동기화가 필요하다는 뜻이다.

 

그러나 최소힙에서 만약 10이 빠졌다고 해도, 최대 힙에서 이 값을 실질적으로 제거할 수 있는 방법은 없다. 따라서 나는 상태를 기록하기로 했다. 

 

"10이라는 값은 최대힙에 있더라도 실질적인 요소가 아니다" 라고 말이다. 

 

이런 상태를 기록할 수 있는 맵을 하나 만들어서, 최대힙이나 최소힙에서 값을 빼게 될 때 맵에 기록해줬다.

 

이 맵은 "D -1"이나 "D 1"계산을 통해서 값을 뺄때에도 유효한 값인지 검사할 때 쓰이며, 마지막에 최댓값과 최솟값을 구할때에도 유효한 값인지 검사한다.

 

결과적으로 최대힙, 최소힙 두개를 두고, 요소의 동기화를 위해 맵을 활용하면 풀 수 있다.

 

코드

import java.util.*;

class Solution {
    
    public int getTarget(PriorityQueue<Integer> pq, Map<Integer, Integer> m){
        while(pq.peek() != null){
            // 값이 있으면서, 유효한 값이라면.
            if(m.get(pq.peek()) == 1){
                return pq.poll();
            } 
            pq.poll();
        }
        return 0;
    }
    
    public int[] solution(String[] operations) {

        PriorityQueue<Integer> pq_max = new PriorityQueue<>((x, y) -> y - x);
        PriorityQueue<Integer> pq_min = new PriorityQueue<>();
        Map<Integer, Integer> m = new HashMap<>();
        
        for(String oper : operations){
            // min pq
            if(oper.equals("D -1")){
                while(true){
                    if(pq_min.peek() == null) break;
                    if(m.get(pq_min.peek()) == 1) { //유효한 값일 경우.
                        m.put(pq_min.peek(), 0);
                        pq_min.poll();
                        break;
                    }
                    pq_min.poll(); //유효하지 않은 경우
                }
                
            // max pq
            } else if(oper.equals("D 1")){
                while(true){
                    if(pq_max.peek() == null) break;
                    if(m.get(pq_max.peek()) == 1) { //유효한 값일 경우.
                        m.put(pq_max.peek(), 0);
                        pq_max.poll();
                        break;
                    }
                    pq_max.poll(); //유효하지 않은 경우
                }
            } else{
                Integer val = Integer.parseInt(oper.split(" ")[1]);
                pq_min.add(val);
                pq_max.add(val);
                m.put(val, 1);
            }
        }

        int max_value = getTarget(pq_max, m);
        int min_value = getTarget(pq_min, m);
        
        int[] answer = {max_value, min_value};
        return answer;
    }
}

 

후기

큐라고 알려주니 금방 푼 거 같다...