[프로그래머스/Java] 이중우선순위큐(heap 문제) 풀이

프로그래머스 알고리즘 고득점 Kit의 heap 문제 중 하나인 이중우선순위큐를 자바로 풀어보았다. 

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

프로그래머스

 

 

 처음에는 heap 문제이니까, 어떻게 해서든 자바에 내장된 priority queue를 이용해서 풀어보려 했다. priority queue 두 개를 활용하여, 각각 오름차순, 내림차순으로 설정해 두고 시도해 봤는데, 결국 peek 값에만 접근할 수 있다는 한계에 부딪혀 실패했다. 

 그래서 그냥 insert하면 정렬이 되고, 양방향의 peek 값에 접근이 가능한 double heap을 직접 구현해서 사용했다. 기능적인 면은 deque와 priority queue를 합친 것이라고 보면 된다. 

 그래서 DoubleHeap이라는 클래스를 생성하여, linked list를 이용하여 insert를 할 때는 오름차순 정렬을 지키며 삽입하고, delete를 할 때는 min인지 max인지에 따라 pollFirst나 pollLast를 사용했다. LinkedList가 queue나 stack으로 사용될 수도 있기 때문에 이미 자바에서 stack이나 queue에 관한 메서드를 함께 제공했기 때문에 구현에 큰 어려움은 없었다. 정렬 같은 경우는 이진탐색으로 시도하는 등 다른 방식을 사용했으면 더 시간적으로 효율성을 추구할 수 있지만, 코딩테스트는 보통 빠른 시간 내에 작성해야 하므로 우선 앞에서부터 탐색하여 넣는 방식을 선택했다. 

 이렇게 DoubleHeap만 구현해 두면 나머지는 간단하다. operations의 요구사항에 따라 구현해 둔 메서드를 실행해주기만 하면 된다. 다만, insert를 할 때 string으로 나와 있는 "I {int number}"에서 숫자만 분리해서 int 값으로 변환해야 하기 때문에, 우선 공백을 기준으로 split 해주고 이 중 두 번째 값(인덱스 1)을 선택하여 Integer.parseInt로 int 타입 값으로 바꿔주었다. 

 마지막으로 최소/최대값을 넣어서 리턴해주면 된다. 이것 때문에 원래는 DoubleHeap 클래스 내의 delete 메서드들을 delete 하는 int 값을 리턴하는 메서드로 만들어 마지막에도 활용해주려 했는데, 그렇게 되면 값이 하나만 남아있는 경우 오류가 발생할 수 있다. (값이 하나만 남아있다면, 최솟값과 최댓값이 모두 해당 값일 것이기 때문이다.) 따라서 값을 넣을 때, poll이 아닌 peek 메서드를 사용했다. 

import java.util.*;
import java.lang.*;

class DoubleHeap {
    LinkedList<Integer> heap = new LinkedList<Integer>();
    
    public void insert(int num) {
        int i = 0;
        for (int h : heap) {
            if (h > num) break;
            i++;
        }
        heap.add(i, num);
    }
    
    public void deleteMin() {
        if (!heap.isEmpty()) {
            heap.pollFirst();
        }
    }
    
    public void deleteMax() {
        if (!heap.isEmpty()) {
            heap.pollLast();
        }
    }
}

class Solution {
    public int strToInt(String oper) {
        return Integer.parseInt(oper.split(" ")[1]);
    }
    
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        DoubleHeap dh = new DoubleHeap();
        
        for (String oper : operations) {
            switch (oper) {
                case "D -1":
                    dh.deleteMin();
                    break;
                case "D 1":
                    dh.deleteMax();
                    break;
                default: //Insert
                    dh.insert(Integer.parseInt(oper.split(" ")[1]));
            }
        }
        
        if (!dh.heap.isEmpty()) {
            answer[0] = dh.heap.peekLast();
            answer[1] = dh.heap.peekFirst();
        }
        return answer;
    }
}

 

 

 

 이렇게 구현해두고, 다른 사람들의 코드를 보니, 내가 처음에 시도했던 방식, 즉 우선순위 큐 두 개를 활용하는 방식으로 성공한 분들이 많았다. 코드도 더 깔끔해서, 이를 바탕으로 나도 다시 작성해 봤다. 

 내가 앞서 작성하면서 실패했던 이유는 아주 간단한 자바의 규칙 중 하나를 잊고 있었기 때문이었다. PriorityQueue라고 하더라도 타입이 Queue로 설정되어 있으면, Queue의 메서드도 사용할 수 있다. 그 간단한 사실을 잊어서, peek 외 다른 값에 접근하지 못하는 문제 때문에 실패했다. 이 포인트만 잡은 후 다시 문제를 풀기 시작했다. 

 중요한 점은 PriorityQueue를 선언할 때, Queue 타입으로 선언한다는 점이다. 이렇게 되면, 두개의 우선순위큐를 선언해 두고, 하나에서 poll 할 때 나머지 하나에서는 해당 값을 찾아서 삭제해 버리면 그만이다. 즉, 한쪽에서는 poll 메서드를, 다른 한쪽에서는 remove 메서드를 사용하면 되는 것이다. 이 외 부분은 앞선 코드와 유사하다. 

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        Queue<Integer> maxpq = new PriorityQueue<Integer>(Collections.reverseOrder());
        Queue<Integer> minpq = new PriorityQueue<Integer>();
        
        for (String oper : operations) {
            switch(oper) {
                case "D 1": //delete max
                    if (!maxpq.isEmpty()) 
                        minpq.remove(maxpq.poll());
                    break;
                case "D -1": //delte min
                    if (!minpq.isEmpty())
                        maxpq.remove(minpq.poll());
                    break;
                default: // insert
                    int num = Integer.parseInt(oper.split(" ")[1]);
                    minpq.add(num);
                    maxpq.add(num);
            }
        }
        
        if (!minpq.isEmpty()) {
            answer[0] = maxpq.poll();
            answer[1] = minpq.poll();
        }
        return answer;
    }
}