[알고리즘] 프로그래머스 > 힙 > 이중우선순위큐

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어 수신 탑(높이)
I 숫자 큐에 주어진 숫자를 삽입합니다.
D 1 큐에서 최댓값을 삭제합니다.
D -1 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

프로그래머스

나의 풀이 (java)

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> maxQue = new PriorityQueue(Collections.reverseOrder());
        PriorityQueue<Integer> minQue = new PriorityQueue();

        for (String str:operations) {
            String[] operation = str.split(" ");
             if(operation[0].equals("I")) { // insert
                 maxQue.add(Integer.parseInt(operation[1]));
                 minQue.add(Integer.parseInt(operation[1]));
             }else if (operation[0].equals("D")){ // delete
                 if(maxQue.size()==0) continue;

                 if("1".equals(operation[1])){  // 최대값 삭제 및 동기화
                     minQue.remove(maxQue.remove());
                 }else if("-1".equals(operation[1])){ // 최소값 삭제 및 동기화
                     maxQue.remove(minQue.remove());
                 }
             }
        }
        answer[0] = maxQue.size()>0 ? maxQue.remove():0;
        answer[1] = minQue.size()>0 ? minQue.remove():0;
        return answer;
    }
}

풀이 방법

• (정렬된) 우선순위 큐를 2개 사용해서, 최소/최대값 관리
• 2개의 큐의 동기화 (remove를 이용)

다른사람의 풀이 (java)

.

import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
    public int[] solution(String[] arguments) {
        MidV q = new MidV();

        for(int i = 0; i < arguments.length; i++){
            String[] commend = arguments[i].split(" ");

            int v = Integer.parseInt(commend[1]);
            if(commend[0].equals("I")){
                q.push(v);
            }else{
                switch (v){
                    case 1 : q.removeMax();
                    break;
                    case -1: q.removeMin();
                    break;
                }
            }
        }


        int[] aw = new int[]{q.getMaxValue(),q.getMinValue()};

        return aw;
    }
}

class MidV{
    private PriorityQueue<Integer> leftHeap;
    private PriorityQueue<Integer> rightHeap;

    public MidV(){
        leftHeap = new PriorityQueue<>(10,Collections.reverseOrder());//최대값;
        rightHeap = new PriorityQueue<>();//최소값
    }


    public void push(int v){
        leftHeap.add(v);
    }

    public void removeMax(){

        while(!rightHeap.isEmpty()){
            leftHeap.add(rightHeap.poll());
        }

        leftHeap.poll();
    }

    public void removeMin(){

        while(!leftHeap.isEmpty()){
            rightHeap.add(leftHeap.poll());
        }

        rightHeap.poll();
    }

    public int getMaxValue(){

        if(leftHeap.size() == 0 && rightHeap.size() == 0)
            return 0;

        while(!rightHeap.isEmpty()){
            leftHeap.add(rightHeap.poll());
        }

        return leftHeap.peek();
    }

    public int getMinValue(){

        if(leftHeap.size() == 0 && rightHeap.size() == 0)
            return 0;

        while(!leftHeap.isEmpty()){
            rightHeap.add(leftHeap.poll());
        }

        return rightHeap.peek();
    }

}

Good Idea : 클래스를 만들어 객체로 관리

느낀점

• (우선순위) 큐의 동작원리는 잘 알고 가자!
  • 노드 추가/삭제: add/remove