[프로그래머스] 힙(Heap) - 이중우선순위큐 문제 풀이

오늘은 프로그래머스에서 힙(Heap) 문제 중 이중우선순위큐 문제 풀이를 해보겠습니다. 문제에서 이미 해결 방법이 나와있어보이지만 처음 들어보는 자료구조인 이중 우선순위 큐이므로 문제를 이해하는 것부터 알고리즘 만들기, 코드 구현까지 천천히 진행해보겠습니다.

 

 

프로그래머스 > 힙(Heap) > 이중우선순위큐 문제 풀이

 

 

 

 

★ 문제 정보

• 문제명: 이중우선순위큐
• 문제 난이도: Level 3
• 문제 푼 사람수: 12419명
• 사용 가능 언어: 11개 (JavaScript 사용)

 

 

 

 

★ 문제 설명

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

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

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

 

 

이중 우선순위 큐는 바로 큐에 들어있는 최댓값과 최솟값을 모두 삭제할 수 있는 자료구조였습니다. 이 자료구조에 데이터를 삽입하고 최댓값, 최솟값을 삭제하여 남아있는 큐의 최댓값, 최소값을 반환하는 문제입니다.

그럼 문제 정리해보겠습니다.

• 이중 우선순위 큐에 대해 명령어를 모두 수행한 큐의 최댓값, 최솟값 반환하기
• 이중 우선순위 큐 명령어
  • "I 숫자": 큐에 숫자 삽입
  • "D 1": 최댓값 삭제
  • "D -1" 최솟값 삭제
• Input
  • operations: 이중 우선순위 큐의 명령어 리스트
• Output: 모든 명령어 처리 후의 이중 우선순위 큐의 [최댓값, 최솟값] (비어있으면 [0,0])

 

 

 

 

★ 제한 사항

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

 

 

• 1 ≤ operations의 길이(N) ≤ 1,000,000
• 명령어는 "명령어 데이터" 의 구조이며, 최댓값/최솟값은 하나만 삭제
• 빈 큐에 대한 데이터 삭제 명령은 무시

 

 

 

 

★ 입출력 예

operations	return
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

 

 

 

 

★ 입출력 예 설명

입출력 예 #1

 · 6과 -5643을 삽입합니다.
 · 최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
 · 최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
 · 우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
 · 123을 삽입합니다.
 · 최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.

따라서 [0, 0]을 반환합니다.

입출력 예 #2

 · -45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다.
 · -642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다.
 · 333을 삽입합니다.

이중 우선순위 큐에 -45, 45, 333이 남아있으므로, [333, -45]를 반환합니다.

 

 

 

 

★ 알고리즘 만들기

1. 이중우선순위큐가 될 배열을 선언한다.
2. 연산 명령어를 순회하며 삽입 명령과 삭제 명령을 수행한다.
   2-1. 삽입 명령 시, 배열에 값을 추가한다.
   2-2. 삭제 명령 시, 배열을 정렬하여 최댓값 or 최솟값을 삭제한다.
3. 모든 명령어를 수행한 이중우선순위큐의 결과를 반환한다.

 

 

이번 문제는 제목이 이중우선순위큐였지만, 자료구조는 배열을 활용하였습니다.

 

이중우선순위큐에 대한 최대 길이가 크지 않을 것을 고려한 자료구조 선정이었습니다. 또한, 실제 우선순위 큐의 삽입 / 삭제 시간복잡도인 O(logN)과 비교하여 배열은 삽입은 O(1), 삭제는 최댓값은 O(N), 최솟값은 O(1)로 비교적 나쁘지 않은 시간이 소요된다고 판단되었습니다.

이 때 삭제 명령 수행 시 필요한 배열의 정렬에 대한 시간복잡도인 O(NlogN)이 문제였지만 이 수행을 최소화하는 알고리즘을 통해 극복해보고자 하였습니다.

 

※ 위 알고리즘이 최선은 아닐 수도 있기에 문제 풀이에 참고만 하시기 바랍니다.

 

 

 

 

★ 코드 구현

function solution(operations) {
    var answer = [];
    // 1. 이중우선순위큐가 될 배열을 선언한다.
    const dualPriorityQueue = [];
    let isSorted = false;

    // 2. 연산 명령어를 순회하며 삽입 명령과 삭제 명령을 수행한다.
    for(let i = 0; i < operations.length; i++) {
        const [operation, number] = operations[i].split(" ");
        // 2-1. 삽입 명령 시, 배열에 값을 추가한다.
        if(operation === "I") {
            dualPriorityQueue.push(parseInt(number));
            isSorted = false;
        // 2-2. 삭제 명령 시, 배열을 정렬하여 최댓값 or 최솟값을 삭제한다.
        } else {
            if(!isSorted) {
                dualPriorityQueue.sort((a, b) => a - b);
            }

            if(number === '1') {
                dualPriorityQueue.pop();
            } else {
                dualPriorityQueue.shift();
            }
        }
    }

    if(!isSorted) {
        dualPriorityQueue.sort((a, b) => a - b);
    }

    // 3. 모든 명령어를 수행한 이중우선순위큐의 결과를 반환한다.
    if(dualPriorityQueue.length > 0) {
        answer = [dualPriorityQueue[dualPriorityQueue.length - 1], dualPriorityQueue[0]];
    } else {
        answer = [0,0];
    }

    return answer;
}

 

 

 

 

★ 채점 결과

 

 

이중우선순위큐 문제 풀이의 채점 결과는 정확성 테스트 케이스 6개를 통과하여 문제 풀이를 완료하였습니다.

그럼 다음 문제 풀이로 돌아오겠습니다.