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

---

프로그래머스 Lv3 - 이중우선순위큐 문제

프로그래머스 알고리즘 고득점 Kit 카테고리의 힙 문제 중 레벨 3 이중우선순위큐 문제를 풀이했다.

단순하게 오름차순의 정렬을 가지는 우선순위큐(front가 최솟값을 가리키는)를 하나 생성하고,
switch ~ case문을 통해 삽입, 삭제 연산을 분리, 삭제 연산 중 최솟값 삭제는 우선순위큐의 remove()메소드를 사용하여 front가 가리키는 최솟값을 삭제, 최댓값 삭제는 removeMax()라는 메소드를 정의하여 최댓값을 삭제할 수 있는 로직을 구성해 문제를 풀이했다. 문제 레벨이 3단계로 들어가 있긴 하지만 내가 풀어본 다른 3단계문제들 보다는 그래도 쉬운편에 속했다.

풀이 후 다른 사람의 풀이를 보니
1. 오름차순, 내림차순 정렬을 가지는 우선순위 큐(각각 최소값, 최대값이 front인)를 두 개 생성
2. 삽입 연산시에는 두 큐에 모두 값을 삽입하고 삭제 연산시에는 최소값, 최대값 삭제 별로 해당하는 큐에서만 remove() 메소드를 사용
3. 정답 추출 시 최소값은 오름차순 큐에서 poll, 최대값은 내림차순 큐에서 poll하여 리턴

정확한 테스트는 하지 않았지만, 내 코드는 큐 객체가 다른 사람의 풀이보다 자주 생성, 소멸하기 때문에 생성 비용이 더 많아 성능에 약간 차이가 있을 것 같다!

DoublePriorityQueue.java

package com.example.Programmers.Lv3;

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

/**
 * 프로그래머스 Lv3 - 이중우선순위큐
 * Heap문제 우선순위 큐 활용 풀이
 */
public class DoublePriorityQueue {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (String s : operations) {
            String[] sArr = s.split(" ");
            switch (sArr[0]) {
                // 삽입 연산
                case "I":
                    pq.add(Integer.parseInt(sArr[1]));
                    break;
                // 삭제 연산
                case "D":
                    if (!pq.isEmpty()) {
                        // 최소값 삭제
                        if (sArr[1].equals("-1")) {
                            pq.remove();
                            // 최대값 삭제
                        } else {
                            pq = removeMax(pq);
                        }
                    }
                    break;
                default:
                    break;
            }
        }

        if (!pq.isEmpty()) {
            // 최소값 정답 배열에 삽입
            answer[1] = pq.poll();
            PriorityQueue<Integer> descPq = new PriorityQueue<>(Collections.reverseOrder());
            while (!pq.isEmpty()) {
                descPq.add(pq.poll());
            }
            // 최대값 정답 배열에 삽입
            answer[0] = descPq.poll();
        }
        return answer;
    }

    // 최대값 삭제 메소드
    private PriorityQueue<Integer> removeMax(PriorityQueue<Integer> pq) {
        PriorityQueue<Integer> descPq = new PriorityQueue<>(Collections.reverseOrder());

        // 내림차순 우선순위 큐에 내림차순으로 정렬되어 있는 데이터를 재정렬
        while (!pq.isEmpty()) {
            descPq.add(pq.poll());
        }
        // 가장 큰 값 삭제후 다시 내림차순 정렬하여 리턴
        descPq.remove();
        PriorityQueue<Integer> newPq = new PriorityQueue<>();
        while (!descPq.isEmpty()) {
            newPq.add(descPq.poll());
        }

        return newPq;
    }
}

DoublePriorityQueueTest.java

package com.example.Programmers.Lv3;

import static org.junit.Assert.assertArrayEquals;

import org.junit.Test;

public class DoublePriorityQueueTest {
    @Test
    public void testDoublePriorityQueue() {
        DoublePriorityQueue dpq = new DoublePriorityQueue();

        int[] result1 = dpq.solution(new String[] { "I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1" });
        int[] result2 = dpq
                .solution(new String[] { "I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333" });

        int[] expected1 = new int[] { 0, 0 };
        int[] expected2 = new int[] { 333, -45 };

        assertArrayEquals(expected1, result1);
        assertArrayEquals(expected2, result2);
    }
}