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

이중우선순위큐 문제는 프로그래머스 코딩테스트 연습 Heap에 있습니다.
https://programmers.co.kr/learn/courses/30/lessons/42628

저는 개발자 지망생으로 공부하고 있는 대학생입니다.
때문에 아직 많이 부족합니다.

아래의 코드가 해당 문제를 풀 수 있는 코드는 맞지만, 해당 문제를 풀기위한 가장 좋은 코드는 아닙니다.
코드에 문제가 있거나, 부족한 점이 있다면 댓글 달아주시면 감사히 배우겠습니다.
감사합니다.

이중우선순위큐 문제

해당 문제는 말 그대로 이중우선순위큐를 만드는 문제입니다.
이중우선순위큐라는 것은 삽입,최대값 제거, 최솟값 제거가 모두 가능한 자료구조를 의미합니다.

해당 문제에서는
operations로 주어지는 명령어를 읽어
"I 숫자"의 조합인 경우 해당 숫자를 삽입하고
"D 1"의 조합인 경우 최댓값을 제거하며
"D -1"의 조합인 경우 최솟값을 제거하는 연산을 진행합니다.

주어지는 데이터와 return해야하는 값은 아래와 같습니다.

operations	return
["I 16","D 1"]	[0,0]
["I 7","I 5","I -5","D -1"]	[7,5]

만약 이중우선순위큐에 값이 존재하지 않는 경우 [0,0]을 반환합니다.

자세한 문제의 내용은 프로그래머스에서 확인하실 수 있습니다.

전체 코드

우선 제 전체 코드입니다.

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

class Solution {
    public int[] solution(String[] operations) {
        // 내림차순, 오름차순으로 각각 하나씩 Heap을 만든다.
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        PriorityQueue<Integer> reversePriorityQueue = new PriorityQueue<>(Collections.reverseOrder());

        int index = 0; // 현재 이중우선순위큐에 존재하는 값의 수
        for (String operation : operations) {
            // operation을 문자와 숫자로 구분한다.
            String[] operationData = operation.split(" ");

            // 값을 추가하는 경우
            if(operationData[0].equals("I")) {
                // 모든 Heap에 값을 추가한다.
                priorityQueue.offer(Integer.parseInt(operationData[1]));
                reversePriorityQueue.offer(Integer.parseInt(operationData[1]));
                index++;
            }
            // 값을 제거하는 경우
            else {
                if (index > 0) {
                    index--;
                    // 명령어에 따라 특정 Heap에서 값을 제거한다.
                    if (operationData[1].equals("1")) {
                        reversePriorityQueue.poll();
                    } else {
                        priorityQueue.poll();
                    }
                }
            }
            // index가 0인경우, 내부에 데이터가 없어야 하지만 실제로는 데이터가 나누어져 들어가 있기 때문에, 이후에 추가 및 제거시 문제가 생길 수 있어 초기화한다.
            if(index <= 0) {
                priorityQueue = new PriorityQueue<>();
                reversePriorityQueue = new PriorityQueue<>(Collections.reverseOrder());
            }
        }
        if(index == 0) {
            return new int[]{0,0};
        }
        else {
            return new int[]{reversePriorityQueue.poll(), priorityQueue.poll()};
        }
    }
}

풀이 방법

제가 풀이한 방법은 이중우선순위큐인 만큼, 우선순위큐를 2번 사용하는 방식입니다.

즉 내림차순, 오름차순의 우선순위큐를 각각 만들어 하나의 자료구조처럼 활용하는 것입니다.

1. PriorityQueue 2개 선언

앞서 말씀드린대로 우선순위큐를 2번 사용하여, 구성하였습니다.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
PriorityQueue<Integer> reversePriorityQueue = new PriorityQueue<>(Collections.reverseOrder());

2. operation이 I로 시작하는 경우, 데이터 삽입

operation이 "I"로 시작하는 경우, 뒤에 나오는 숫자를 Integer로 변경하여, 두가지 우선순위큐에 모두 넣어주고, 현재 이중우선순위큐 내부의 데이터의 갯수를 의미하는 index를 증가시킵니다.

if(operationData[0].equals("I")) {
                // 값을 추가하는 경우 둘 다 추가한다.
                priorityQueue.offer(Integer.parseInt(operationData[1]));
                reversePriorityQueue.offer(Integer.parseInt(operationData[1]));
                index++;
            }

3. operation이 D로 시작하는 경우

operation이 "D"로 시작하는 경우, 뒤에 나오는 값이 -1이면, 오름차순의 우선순위큐의 값을, 1이라면 내림차순의 우선순위큐의 값을 제거합니다.
이후 index를 -1해줍니다.

이때 주의할점으로는 index의 크기 즉 현재 가지고 있는 값이 존재할 때만, 해당 연산이 가능하다는 것입니다.

else {
	if (index > 0) {
        index--;
        // 값을 제거하는 경우, 뒤 숫자에 따라 다른 queue를 사용한다.
   		if (operationData[1].equals("1")) {
            reversePriorityQueue.poll();
        } 
        else {
            priorityQueue.poll();
        }
	}
}

4. 내부에 값이 없을 때, 초기화

이부분에서 index가 필요한 이유인데,

만약 중간에 index값이 0이 되었다가 새로운 값을 추가한다고 하면, 현재 제 코드상으로는 두개의 우선순위큐를 사용하고 있기 때문에 아직 각각 큐에 값이 남아있게 됩니다.

그렇게 되면, 이후 값을 추가 했을 때 정렬에 문제가 발생할 수 있기 때문엔 이때, 두 우선순위 큐의 값을 초기화해주었습니다.

예를 들어

I 1, I 3, D -1, D 1을 한다면, 이중우선순위큐에서는 내부에 값이 없어야하지만, 제 구현에 따르면 두가지 우선순위큐에 각각 1과 3이 남아있게 됩니다.

이때, I 4를 하고, D -1을 한다면, 내림차순 우선순위큐에 남아있던 1이 4보다 더 작기 때문에, 4가 아니라 1이 빠져나가게 됩니다.

이를 막기위한 코드라고 생각하시면 될 것 같습니다.

// index가 0이 된 이후 다른 값이 들어왔을 때 초기화를 하지 않으면 꼬일 수 있다.
if(index <= 0) {
	priorityQueue = new PriorityQueue<>();
	reversePriorityQueue = new PriorityQueue<>(Collections.reverseOrder());
	}
}