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

1. 문제

문제 링크

2. 풀이

문제를 푸는 방법은 세 가지가 있습니다.

1. 우선순위큐를 이용

이 문제의 제목답게 우선순위큐를 이용해서 문제를 푸는 방식을 생각해봅시다.
문제를 해결하기 위해 우선순위큐가 두 개가 필요하겠네요.
하나는 최소힙으로 구현된 우선순위큐,
하나는 최대힙으로 구현된 우선순위큐 이렇게요.

이 두 개의 큐가 있다면 데이터 삽입 명령에는 두 개의 힙에 넣어주고
최댓값 삭제 명령에는 최대힙 우선순위큐에서 데이터를 poll한 데이터를
최소힙 우선순위큐에서 제거하고
최솟값 삭제 명령에는 최소힙 우선순위큐에서 데이터를 poll한 데이터를
최대힙 우선순위큐에서 제거하면 됩니다.

이제 남은 건 최소힙과 최대힙의 구현입니다.

JAVA 기준으로 우선순위큐는 최소힙으로 구현되어 있습니다.
즉, 루트 노드가 가장 작은 값을 보장하는 트리죠.
그렇다면 최대힙은 우선순위큐에 넣을 데이터를 부호를 바꿔서 넣으면 되지 않을까요?
예를 들어 10을 -10으로 넣는 겁니다.
그러면 poll 했을 때만 다시 부호를 바꾼다면 간단하게 최대힙을 구현할 수 있겠네요.

전체 코드

import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
    public int[] solution(String[] operations) {
   	Queue<Integer> minHeap = new PriorityQueue<>(); // 최소힙
	Queue<Integer> maxHeap = new PriorityQueue<>(); // 최대힙

	for (int i = 0; i < operations.length; i++) {
            // 데이터 삽입
	    if (operations[i].charAt(0) == 'I') { 
	        int data = Integer.parseInt(operations[i].split(" ")[1]);
		minHeap.add(data);
		maxHeap.add(-data); // 최대힙은 부호를 바꿔서 넣기
	    } 
            // 최대값 삭제
	    else if (!minHeap.isEmpty() && operations[i].equals("D 1")) { 
                // 서로 부호가 반대이므로 poll할 때 부호 전환
		minHeap.remove(-maxHeap.poll()); 
            }
            // 최소값 삭제
	    else if (!minHeap.isEmpty() && operations[i].equals("D -1")) { 
                // 서로 부호가 반대이므로 poll할 때 부호 전환
		maxHeap.remove(-minHeap.poll()); 
            }
	}
        
        // 최대힙은 poll할 때 부호를 원래 부호로 바꿔줌
	return minHeap.isEmpty() ? new int[] {0, 0} : new int[] {-maxHeap.poll(), minHeap.poll()};
    }
}

이 방법은 특정 데이터에 해당하는 개체를 제거해야하기 때문에
특정 개체를 찾는데 o(N)의 시간과 제거에는 o(logN)의 시간이 걸리고
이를 N번 반복하기 때문에 대략 o(N^2logN)의 시간 복잡도를 가집니다.

2. 정렬을 이용

1번 방법으로 풀어도 우선순위큐를 이용한 보람이 적군요.
결국 제거 연산이 o(NlogN)의 시간이 걸리기 때문이죠.
이는 퀵소트나 머지소트의 시간 복잡도와 동일합니다.

그렇다면 배열 하나만 선언해서 데이터를 넣어주고
삭제 명령할 때만 정렬을 한 후
최댓값 삭제일 때는 맨 뒤의 요소를,
최솟값 삭제일 때는 맨 앞의 요소를 제거해주면
문제에서 원하는 이중우선순위큐를 구현할 수 있습니다.

전체 코드

function solution(operations) {
    const pq = [];

    operations.forEach(operation => {
        let [cmd, num] = operation.split(' ');
        
        // 데이터 삽입
        if (cmd == 'I') {
            pq.push(Number(num));
        }
        // 데이터 삭제
        else if (pq.length) {
            // 정렬을 한 후에
            pq.sort((a, b) => a - b);
            
            // 최댓값 삭제일 때는 맨 뒤의 요소를,
            // 최솟값 삭제일 때는 맨 앞의 요소를 제거
            pq[num == 1 ? 'pop' : 'shift']();
        }
    });
    
    // 마지막으로 정렬한 후에 리턴
    pq.sort((a, b) => a - b);
    return pq.length ? [pq[pq.length - 1], pq[0]] : [0, 0];
}

이 방법은 정렬하는데 o(NlogN)의 시간이 걸리고
최댓값이나 최소값을 제거하는데 o(N)의 시간이 걸리고
이를 N번 반복하기 때문에 대략 o(N^3logN)의 시간이 걸립니다.

흠 결국에는 우선순위큐를 이기지 못하는 군요.
제거 연산에 o(N)의 시간이 소요되는 이유는
내부적으로 배열을 복사하는 연산이 들어있기 때문이죠.

최댓값 제거에는 o(1)의 시간만 필요하지만
최솟값 제거에는 1번 index부터 (size - 1)번 index까지의 데이터를
0번 index부터 (size -2)번 index까지 복사해야하기 때문에
시간이 많이 소요됩니다.

3. 리스트를 이용

2번 방법과 비슷한 풀이입니다.
2번 방법을 보신 분들중 몇몇 분들은 알아채셨는지도 모르겠습니다.
'굳이 정렬해야돼?' 라고 말이죠.
맞습니다. 정렬을 하지 않아도 최댓값과 최솟값을 찾아내는데 무리가 없습니다.
오히려 더 빠르죠.

선형으로 0번 index부터 (size - 1)번 index까지 탐색해서
최댓값이나 최솟값이 위치하는 index를 찾은 다음
그 index에 해당하는 요소를 리스트에서 제거합니다.

전체 코드

function solution(operations) {
    const pq = [];

    operations.forEach(operation => {
        let [cmd, num] = operation.split(' ');
        
        // 데이터 삽입
        if (cmd == 'I') {
            pq.push(Number(num));
        }
        // 데이터 삭제
        else if (pq.length) {
            const removeElem = Math[num == 1 ? 'max' : 'min'](...pq);
            const removeIndex = pq.findIndex(elem => elem == removeElem);
            pq.splice(removeIndex, 1);
        }
    });
      
    return pq.length ? [Math.max(...pq), Math.min(...pq)] : [0, 0];
}

이 방법은 최댓값이나 최솟값을 찾는데 o(N)의 시간이 걸리고
삭제하는데 o(N)의 시간이 걸리고
이를 총 N번 반복하기 때문에 총 o(N^3)의 시간이 걸립니다.