[Programmers] 이중우선순위큐 - JAVA

📚 Problem

이중우선순위큐

• I 숫자 큐에 주어진 숫자를 삽입합니다
• D 1 큐에서 최댓값을 삭제합니다
• D -1 큐에서 최솟값을 삭제합니다
• 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 구하기

📝 Solution

Key Idea

• 오름차순으로 정렬이 되는 우선순위큐와 내림차순으로 정렬이 되는 우선순위큐 각각 1개씩을 사용합니다
• 삽입할 때에는 두 곳에 모두 삽입을 해줍니다
• 큐에서 최댓값을 삭제할 때에는 내림차순 우선순위큐에서 제일 앞의 값을 꺼내고 오름차순 큐에서 해당 값을 remove() 해줍니다
• 큐에서 최솟값을 삭제하는 것은 위의 방법의 반대로 진행합니다

PriorityQueue<Integer> increase = new PriorityQueue<>((o1, o2) -> o1 - o2);
PriorityQueue<Integer> decrease = new PriorityQueue<>((o1, o2) -> o2 - o1);

for (String operation : operations) {
    String[] tokens = operation.split(" ");

    switch (tokens[0]) {
        case "I" :
            insert(increase, decrease, tokens[1]);
            break;
        case "D" :
            delete(increase, decrease, tokens[1]);
    }
}

💻 Code

Solution.java

import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> increase = new PriorityQueue<>((o1, o2) -> o1 - o2);
        PriorityQueue<Integer> decrease = new PriorityQueue<>((o1, o2) -> o2 - o1);

        for (String operation : operations) {
            String[] tokens = operation.split(" ");

            switch (tokens[0]) {
                case "I" :
                    insert(increase, decrease, tokens[1]);
                    break;
                case "D" :
                    delete(increase, decrease, tokens[1]);
            }
        }
        return find(increase, decrease);
    }

    private void insert(PriorityQueue<Integer> increase, PriorityQueue<Integer> decrease, String num) {
        increase.add(Integer.parseInt(num));
        decrease.add(Integer.parseInt(num));
    }

    private void delete(PriorityQueue<Integer> increase, PriorityQueue<Integer> decrease, String num) {
        if (num.equals("1") && !decrease.isEmpty()) {
            int current = decrease.poll();
            increase.remove(current);
        } else if (num.equals("-1") && !increase.isEmpty()) {
            int current = increase.poll();
            decrease.remove(current);
        }
    }

    private int[] find(PriorityQueue<Integer> increase, PriorityQueue<Integer> decrease) {
        int[] answer = new int[2];

        if (increase.isEmpty() || decrease.isEmpty())
            return answer;

        answer[0] = decrease.poll();
        answer[1] = increase.poll();

        return answer;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int[] result = solution.solution(new String[]{"I 16","D 1"});
        assertArrayEquals(new int[]{0,0}, result);
    }

    @Test
    public void solution_2(){
        int[] result = solution.solution(new String[]{"I 7","I 5","I -5","D -1"});
        assertArrayEquals(new int[]{7,5}, result);
    }
}