99클럽 코테 스터디 10일차 TIL 이중우선순위큐

📝 문제

프로그래머스

🔥 시도해본 접근 방식

본 문제는 입력으로 들어온 문자열 배열을 해석하여

1. 숫자를 삽입

2. 최솟값 제거

3. 최댓값 제거

위 명령을 큐를 사용하여 수행하면서 [최댓값, 최솟값]배열을 출력하면 될 것이라고 생각하고 접근하였다.

 

PriorityQueue를 사용하면 최소값을 제거하는 작업은 단순히 poll()을 해주면 되지만,

최댓값을 제거하는 작업은 효율적인 방법이 떠오르지 않아 우선 새로운 PriorityQueue를 선언해 기존 PriorityQueue에서 size - 1 까지 값을 뽑아내어 넣어주는 방식으로 적용하였다.

 

1️⃣ 첫번째 시도

import java.util.PriorityQueue;

class Solution {
    public static int[] solution(String[] operations) {
        // 힙 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (String o : operations) {
            // 큐에서 최대값을 삭제한다.
            if (!pq.isEmpty() && o.equals("D 1")) {
                PriorityQueue<Integer> newPq = new PriorityQueue<>();

                for (int i = 0; i < pq.size() - 1; i++) {
                    newPq.offer(pq.poll());
                }

                pq = newPq;
            }
            // 큐에서 최소값을 삭제한다.
            else if (!pq.isEmpty() && o.equals("D -1")) {
                pq.poll();
            }
            // 큐에 숫자를 삽입힌다.
            else if (o.startsWith("I")) {
                int i = Integer.parseInt(o.substring(2));
                pq.offer(i);
            }
        }

        int size = pq.size();
        int[] answer = new int[]{0, 0};
        for (int i = 0; i < size; i++) {
            int value = pq.poll();

            if (i == 0) {
                answer[1] = value;
            } else if (i == n - 1) {
                answer[0] = value;
            }
        }

        return answer;
    }
}

위와 같이 코드를 작성하여 제출하였지만 테스트 케이스 3개에서 통과되지 못하고 실패하였다.

코드를 실행 하였을때, 입력으로 받은 문자열 배열대로 숫자 입력, 제거 동작이 문제없이 잘 작동하는 것으로 보여지는데 어떤것을 놓치고 있는지 출력을 프린트 해보았더니

입력이 ["I 1", "I 3", "I 5", "I 7", "I 9", "D -1", "D -1", "D 1", "I 2", "D 1", "D 1"]와 같을 때 "D 1" 부분에서 [5, 7, 9] -> [5] 와같이 변하는 결함을 발견하였고 for문의 pq.size()가 반복됨에 따라 값이 변하는 문제가 있음을 깨달았다.

2️⃣ 두번째 시도

import java.util.PriorityQueue;

class Solution {
    public static int[] solution(String[] operations) {
        // 힙 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (String o : operations) {
            // 큐에서 최대값을 삭제한다.
            if (!pq.isEmpty() && o.equals("D 1")) {
                PriorityQueue<Integer> newPq = new PriorityQueue<>();
                
                int size = pq.size();
                for (int i = 0; i < size - 1; i++) {
                    newPq.offer(pq.poll());
                }

                pq = newPq;
            }
            // 큐에서 최소값을 삭제한다.
            else if (!pq.isEmpty() && o.equals("D -1")) {
                pq.poll();
            }
            // 큐에 숫자를 삽입힌다.
            else if (o.startsWith("I")) {
                int i = Integer.parseInt(o.substring(2));
                pq.offer(i);
            }
        }

        int size = pq.size();
        int[] answer = new int[]{0, 0};
        for (int i = 0; i < size; i++) {
            int value = pq.poll();

            if (i == 0) {
                answer[1] = value;
            } else if (i == n - 1) {
                answer[0] = value;
            }
        }

        return answer;
    }
}

따라서 다음과 같이 코드를 수정하였고 다시 제출해보았지만 결과는 동일하였다.

긴 시간 고민에도 원인을 찾을 수 없어 반례 하나를 찾아보았고, 원인을 알 수 있었다.

만약 큐의 사이즈가 1일 때 내 코드는 항상 [0, 최솟값]을 리턴할 것이다 하지만 이 경우에는 최댓값과 최솟값이 같은 값으로 리턴되어야 했다는 것을 깨닫고 코드를 보완하였다.

 ✨ 성공 코드

import java.util.PriorityQueue;

class Solution {
    public static int[] solution(String[] operations) {
        // 힙 선언
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (String o : operations) {
            // 큐에서 최대값을 삭제한다.
            if (!pq.isEmpty() && o.equals("D 1")) {
                PriorityQueue<Integer> newPq = new PriorityQueue<>();

                int size = pq.size();
                for (int i = 0; i < size - 1; i++) {
                    newPq.offer(pq.poll());
                }

                pq = newPq;
            }
            // 큐에서 최소값을 삭제한다.
            else if (!pq.isEmpty() && o.equals("D -1")) {
                pq.poll();
            }
            // 큐에 숫자를 삽입힌다.
            else if (o.startsWith("I")) {
                int i = Integer.parseInt(o.substring(2));
                pq.offer(i);
            }
        }

        int size = pq.size();
        int[] answer = new int[]{0, 0};
        
        for (int i = 0; i < size; i++) {
            int value = pq.poll();
            
            if (i == 0) {
                answer[1] = value;

                // 큐의 사이즈가 1일 수도 있으므로 최댓값도 갱신해준다.
                answer[0] = value;
            } else if (i == size - 1) {
                answer[0] = value;
            }
        }

        return answer;
    }
}

10 회차 까지 문제풀이를 하면서 문제 자체에 대한 이해도가 조금 부족하다는 느낌을 받았다.

다음 부터는 문제에 대해 부족함 없이 이해하기 위한 노력을 많이 기울여야 할 것 같다.

 

사실 내 풀이는 문제의 힌트인 이중우선순위큐의 목적과는 맞지 않은 풀이였다고 생각되는데 다른사람의 풀이를 보고 개인적으로 목적에 가장 부합한 풀이라고 생각하는 풀이는 다음과 같다.

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();
    }

}