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

[문제 설명]

programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

 

[풀이 내용]

JAVA의 PriorityQueue 자료구조를 이용하여 해결하는 문제다. 

이 때 기억해야할 점은 다음 두가지이다. 

1. JAVA의 PriorityQueue는 min heap이 default이다. 

2. max heap을 구현하고 싶다면 Collections.reverseOrder() 옵션을 사용한다. 

 

문제에서 최댓값을 삭제하는 경우와 최솟값을 삭제하는 경우가 둘 다 존재한다. 

min heap과 max heap이 둘 다 존재해야하므로 PriorityQueue 를 2개 생성하였다. 

 

느낀점:

Level3라고 하기엔 너무 쉬운문제다. 그래도 PriorityQueue에 대한 기본 특징을 다시 되짚고 넘어갈 수 있는 문제다. 

 

[JAVA code]

package com.algorithm.programmers.level3;

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

public class Test07 {
    public static void main(String[] args) {
        String[] operations =
                //{"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};
                //{"I 7", "I 5", "I -5", "D -1"};
                //{"I 16","D 1"};
                {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};
        System.out.println(Arrays.toString(solution(operations)));
    }

    public static int[] solution(String[] operations) {
        int[] answer = new int[2];
        String[] commands = {"D 1", "D -1"};
        PriorityQueue<Integer> pq_asc = new PriorityQueue<>(); // min heap
        PriorityQueue<Integer> pq_desc = new PriorityQueue<>(Collections.reverseOrder()); // max heap

        for (int i = 0; i < operations.length; i++) {
            String op = operations[i];

            if (op.startsWith("I")) {
                int num = Integer.parseInt(op.split(" ")[1]);
                pq_asc.add(num);
                pq_desc.add(num);

            } else if (op.equals(commands[0])) {
                if (!pq_desc.isEmpty()) {
                    int max = pq_desc.poll();
                    pq_asc.remove(max);
                }
            } else if (op.equals(commands[1])) {
                if (!pq_asc.isEmpty()) {
                    int min = pq_asc.poll();
                    pq_desc.remove(min);
                }
            }
        }

        int max = pq_desc.isEmpty() ? 0 : pq_desc.poll();
        int min = pq_asc.isEmpty() ? 0 : pq_asc.poll();

        answer[0] = max;
        answer[1] = min;
        return answer;
    }
}