[JAVA] 프로그래머스 이중우선순위큐_힙

 

문제 : 

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

프로그래머스

 

 

접근 : 

 

  - 최소 힙, 최대 힙, 재고 HashMap을 생성한후 I가 들어올 경우 입력한다.

 

  - 만약 D -1 이 입력으로 들어온 경우 최소 힙에서 1개를 뺀후 뺀 값을 HashMap에서 재고 감소시킨다.

 

  - 만약 D 1 이 들어온 경우 최대 힙에서 1개를 뺀후 뺀값을 HashMap에서 재고 감소 시킨다.

 

  - 최대/최소 힙에서 데이터를 빼는 경우 항상 먼저 재고가 1 이상인지 체크 후 감소시킨다

    ( 0 인 경우에는 최대힙에서 해당 원소를 뺐기 때문에 그냥 제거해 준다.)

 

  - 모든 입력이 끝난 후 최소 힙에서 최소값을 꺼낸다 만약 힙이 비어있다면 {0, 0}을 Return 한다

 

  - 최소값을 꺼낸후 최대값을 꺼낸다 만약 힙이 비어있다면 {min, min} 값을 Return 한다.

 

  - 만약 최대 힙에 값이 있다면 {min, max} 값을 Return 한다.

 

 

 

 

* 만약 D-1, D-1 명령이 뒤에 더 있는 경우 결과 (엣지 케이스 확인)

 

 

  코드 구현 : 

 

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    private Integer poll(PriorityQueue<Integer> q, Map<Integer, Integer> stock){
        while(!q.isEmpty() && stock.get(q.peek()) == 0) q.poll();
        if(q.isEmpty()) return null;
        stock.put(q.peek(), stock.get(q.peek())-1);
        return q.poll();
    }

    public int[] solution(String[] operations) {
        Map<Integer,Integer> stock= new HashMap<>();
        PriorityQueue<Integer> min_q = new PriorityQueue<>();
        PriorityQueue<Integer> max_q = new PriorityQueue<>(Comparator.reverseOrder());
        String[] temp;

        int num;
        for(String op : operations){
            temp = op.split(" ");
            if(temp[0].equals("I")){
                num = Integer.parseInt(temp[1]);
                min_q.offer(num);
                max_q.offer(num);
                stock.put(num, stock.getOrDefault(num, 0)+1);
                continue;
            }
            poll((Integer.parseInt(temp[1]) < 0 ? min_q : max_q), stock);
        }
        Integer min = poll(min_q, stock);
        if(min == null) return new int[]{0,0};

        Integer max = poll(max_q, stock);
        if(max == null) return new int[]{min, min};
        
        return new int[]{max, min};
    }
}