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

🔗 문제 링크

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

🤔 문제

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어	수신 탑(높이)
I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

📌 제한 사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

😮 문제 해결 방법

최소 힙과 최대 힙 두개를 생성해서 사용하면 문제를 간단하게 해결할 수 있다.

PriorityQueue는 기본적으로 최소 값이 우선순위 형태이기 때문에 PriorityQueue의 생성 파라미터 값에 Collections.reverseOrder()를 넣어주면 최대 값 우선순위 형태(최대 힙)으로 생성된다.

//최소 힙, 최대 힙
PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());

두 개의 큐(힙)을 생성했다면, 이제 Operation값을 하나씩 가져와서 StringTokenizer token값으로 나누어서 연산과 값을 구분해서 조건에 따라 연산해주면된다.

먼저, 빈 큐에 데이터를 삭제 요청하는 경우 연산을 무시한다고 명시되어 있기 때문에 해당 조건인 경우 continue로 바로 for문을 이어나간다.

//빈 큐에 데이터를 삭제 요청 경우 연산 무시
if (pq.size() < 1 && judge.equals("D"))
		continue;

삽입 연산이 들어온다면 해당 값을 최소 힙과 최대 힙에 각각 넣어준다.

//삽입 시 최소 힙, 최대 힙에 value 넣기
if (judge.equals("I")) {
    pq.offer(value);
    maxPq.offer(value);
    continue;
}

이제 남은 조건은 빈 큐가 아니면서 D연산이 들어오는 경우이므로 value값을 0보다 작은지 아닌지로 판단 후 해당 조건에 맞는 코드를 구현하면된다.

D연산이 들어오는 경우 핵심 포인트는 최소 값 혹은 최대 값을 삭제하는 경우에 연산이 일어나지 않은 다른 큐에서도 해당 원소값을 삭제해줘야 하는 점이다. 다음은 최소 힙에서 삭제하는 경우이다.

//나머지 경우는 D이면서 value값이 1인지 -1인지 이므로
//0보다 작은 경우 최소 힙에서 poll후 최대힙에서 해당 원소 삭제
if(value < 0) {
    int min = pq.poll();
    maxPq.remove(min);
    continue;
}

최소 힙과 마찬가지로 최대 힙에서도 동일한 연산을 하여 최대 힙에서 삭제된 원소를 최소 힙에서 삭제해준다.

//최대 힙에서 poll후 최소힙에서 해당 원소 삭제
int max = maxPq.poll();
pq.remove(max);

마지막으로, 최소 힙과 최대 힙에서 가장 앞 원소를 poll해주면 연산 이후 최댓값과 최솟값이 나오므로 해당 값을 return해주면 문제가 해결된다.

아래는 Java로 구현한 코드이다.

🚩 JAVA 코드

package com.algorithm.Programmers.Lv3;

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

public class Solution_42628 {
    public static void main(String[] args) {
        String[] operations = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};
        solution(operations);
    }

    public static int[] solution(String[] operations) {
        int[] answer = new int[2];
        //최소 힙, 최대 힙
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());

        for (String op : operations) {
            StringTokenizer st = new StringTokenizer(op);
            String judge = st.nextToken();
            int value = Integer.parseInt(st.nextToken());

            //빈 큐에 데이터를 삭제 요청 경우 연산 무시
            if (pq.size() < 1 && judge.equals("D"))
                continue;

            //삽입 시 최소 힙, 최대 힙에 value 넣기
            if (judge.equals("I")) {
                pq.offer(value);
                maxPq.offer(value);
                continue;
            }

            //나머지 경우는 D이면서 value값이 1인지 -1인지 이므로
            //0보다 작은 경우 최소 힙에서 poll후 최대힙에서 해당 원소 삭제
            if(value < 0) {
                int min = pq.poll();
                maxPq.remove(min);
                continue;
            }

            //최대 힙에서 poll후 최소힙에서 해당 원소 삭제
            int max = maxPq.poll();
            pq.remove(max);
        }
        if(pq.size() > 0 ) {
            answer[0] = maxPq.poll();
            answer[1] = pq.poll();
        }
        return answer;
    }
}

📄 정리

• 우선순위 큐를 사용하는 문제가 대부분 default값인 최소 힙을 사용하는 문제이기 때문에 최대 힙을 만들기 위해 Collections.reverseOrder()를 사용해야했다. 이러한 방법을 모른다면 Comparable 인터페이스를 구현해야 했기 때문에 해당 메소드를 아는 것이 빠른 문제해결에 도움이 되었다.