개요
문제 이름: 이중우선순위큐 (42628)
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628
플랫폼: 프로그래머스
알고리즘 분류: 힙(Heap)
소요 시간: 30시간
문제 전문
설명
제한사항
입출력
문제 풀이
해설
이 문제는 이중 우선순위 큐(Double-ended Priority Queue)를 구현하는 문제다. 이중 우선순위 큐는 일반적인 우선순위 큐와 달리, 최댓값과 최솟값을 모두 O(1) 시간 복잡도로 삭제할 수 있는 자료구조다.
이 문제에서는 최대 힙(Max Heap)과 최소 힙(Min Heap)을 활용하여 이중 우선순위 큐를 구현해야 한다. 최대 힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리이고, 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리다. 힙은 일차원 배열을 사용하여 구현할 수 있으며, 배열의 첫 번째 요소(인덱스 0)는 루트 노드가 된다.
문제를 해결하기 위해서는 최대 힙과 최소 힙을 동시에 유지해야 한다. 숫자를 삽입할 때는 최대 힙과 최소 힙에 모두 삽입하고, 최댓값을 삭제할 때는 최대 힙에서 값을 삭제하고, 최솟값을 삭제할 때는 최소 힙에서 값을 삭제한다.
하지만 여기서 주의해야 할 점이 있다. 최대 힙과 최소 힙의 동기화를 유지해야 한다는 것이다. 예를 들어, 최댓값을 삭제할 때 최대 힙에서만 값을 삭제하면, 최소 힙에는 해당 값이 여전히 남아있게 된다. 이는 두 힙의 상태가 일치하지 않는 문제를 발생시킨다.
따라서 삭제 연산 시에는 양쪽 힙에서 모두 해당 값을 제거해야 한다. 이를 위해 삭제 연산 후에는 힙이 비어있는지 확인하고, 비어있다면 두 힙을 초기화하여 동기화를 유지한다. 또한, 삽입과 삭제 과정에서 힙의 속성을 유지하기 위해 bubbleUp(상향 선별)과 bubbleDown(하향 선별) 연산을 수행한다.
문제 해석
- 입력으로 주어지는 연산들을 순차적으로 처리해야 한다.
- I 숫자 연산은 큐에 숫자를 삽입한다.
- D 1 연산은 큐에서 최댓값을 제거한다.
- D -1 연산은 큐에서 최솟값을 제거한다.
- 모든 연산을 처리한 후, 큐가 비어있으면 [0, 0]을, 그렇지 않으면 [최댓값, 최솟값]을 반환해야 한다.
알고리즘 원리
이 문제에서 핵심적으로 사용된 자료구조는 힙(Heap)이다. 힙은 완전 이진 트리의 일종으로, 부모 노드와 자식 노드 간의 대소 관계가 일정한 규칙을 만족하는 자료구조다.
- 최대 힙(Max Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같은 완전 이진 트리
- 최소 힙(Min Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같은 완전 이진 트리
힙의 주요 특징
- 삽입과 삭제 연산의 시간 복잡도가 O(log n)이다.
- 최댓값 또는 최솟값을 O(1) 시간에 찾을 수 있다.
- 배열을 사용하여 효율적으로 구현할 수 있다.
힙 연산의 핵심 알고리즘
- 삽입(push): 새 원소를 힙의 마지막에 추가하고, 힙 속성을 만족할 때까지 부모와 비교하며 위로 올린다(bubble up).
- 삭제(pop): 루트 노드를 제거하고, 마지막 노드를 루트로 옮긴 후, 힙 속성을 만족할 때까지 자식과 비교하며 아래로 내린다(bubble down).
요약
- 이중 우선순위 큐를 구현하기
- 최대 힙과 최소 힙을 이용하여 구현하기
- 삽입(I) 연산 시 최대 힙과 최소 힙에 모두 값을 삽입하기
- 최댓값 삭제(D 1) 연산 시 최대 힙에서 값을 삭제하기
- 최솟값 삭제(D -1) 연산 시 최소 힙에서 값을 삭제하기
- 삭제 연산 후에는 두 힙의 동기화를 유지하기
- 모든 연산 처리 후 큐가 비어있으면 [0,0]을, 비어있지 않으면 [최댓값, 최솟값]을 반환하기
시도
1차 시도 (성공)
// 1차 시도 (성공) - 배열
function solution(operations) {
let queue = []; // 모든 원소를 저장할 배열
for (let op of operations) {
const [command, num] = op.split(" ");
if (command === "I") {
// 삽입 연산
queue.push(Number(num));
queue.sort((a, b) => a - b); // 삽입 후 항상 정렬 상태 유지
} else if (queue.length > 0) {
// 삭제 연산 (큐가 비어있지 않을 때만)
if (num === "1") queue.pop(); // 최댓값(마지막 원소) 삭제
else queue.shift(); // 최솟값(첫 번째 원소) 삭제
}
}
// 결과 반환
return queue.length ? [Math.max(...queue), Math.min(...queue)] : [0, 0];
}이 접근 방식은 간단한 배열을 사용하여 문제를 해결한다.
- 빈 배열 queue를 생성하여 모든 원소를 저장한다.
- 각 연산을 순회하면서 처리한다
- I 명령어: 숫자를 배열에 추가하고 즉시 정렬한다.
- D 1 명령어: 배열의 마지막 원소(최댓값)를 제거한다.
- D -1 명령어: 배열의 첫 번째 원소(최솟값)를 제거한다.
모든 연산을 처리한 후, 배열이 비어있지 않다면 최댓값과 최솟값을 반환하고, 비어있다면 [0, 0]을 반환한다. 이 방법은 직관적이고 구현이 쉽지만, 매 삽입 연산마다 정렬을 수행하기 때문에 시간 복잡도가 높다.
시간 복잡도: O(n log n), 여기서 n은 연산의 수다. 각 삽입 연산마다 정렬을 수행하기 때문에 이런 높은 복잡도가 발생한다.
공간 복잡도: O(n), 여기서 n은 큐에 저장된 원소의 최대 개수다.
사용한 메서드
- split(): 문자열을 특정 구분자로 나누어 배열로 반환한다.
- push(): 배열의 끝에 하나 이상의 요소를 추가하고, 배열의 새 길이를 반환한다.
- sort(): 배열의 요소를 정렬한다. 비교 함수를 인자로 받아 커스텀 정렬을 수행할 수 있다.
- pop(): 배열에서 마지막 요소를 제거하고 그 요소를 반환한다.
- shift(): 배열에서 첫 번째 요소를 제거하고, 제거된 요소를 반환한다.
- Math.max() 및 Math.min(): 주어진 숫자들 중 최댓값과 최솟값을 반환한다.
2차 시도 (실패)
// MaxHeap 클래스는 2차, 3차 공통
class MaxHeap {
// 최대 힙 자료구조를 구현
constructor() {
this.heap = []; // 힙을 배열로 표현, 루트는 인덱스 0에 위치
}
// 새 원소를 힙에 추가하는 메서드
push(value) {
this.heap.push(value); // 새 원소를 배열의 끝에 추가
this.bubbleUp(); // 새로 추가된 원소를 올바른 위치로 이동
}
// 최대값(루트)을 제거하고 반환하는 메서드
pop() {
if (this.isEmpty()) return null; // 힙이 비어있으면 null을 반환
const max = this.heap[0]; // 최대값은 항상 루트(인덱스 0)에 있음
const end = this.heap.pop(); // 배열의 마지막 원소를 제거
if (this.heap.length > 0) {
this.heap[0] = end; // 마지막 원소를 루트로 이동
this.bubbleDown(); // 루트에서 시작해 올바른 위치로 이동
}
return max; // 최대값을 반환
}
// 새로 추가된 원소를 위로 이동시켜 힙 속성을 유지하는 메서드
bubbleUp() {
let index = this.heap.length - 1; // 새로 추가된 원소의 인덱스
const element = this.heap[index]; // 새로 추가된 원소
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2); // 부모 노드의 인덱스
let parent = this.heap[parentIndex]; // 부모 노드의 값
if (element <= parent) break; // 올바른 위치를 찾으면 루프를 종료
// 부모와 현재 원소를 교환
this.heap[parentIndex] = element;
this.heap[index] = parent;
index = parentIndex; // 인덱스를 부모 인덱스로 업데이트
}
}
// 루트에서 시작해 아래로 이동하며 힙 속성을 유지하는 메서드
bubbleDown() {
let index = 0; // 루트에서 시작
const length = this.heap.length;
const element = this.heap[0]; // 현재 검사 중인 원소
while (true) {
let leftChildIndex = 2 * index + 1; // 왼쪽 자식의 인덱스
let rightChildIndex = 2 * index + 2; // 오른쪽 자식의 인덱스
let leftChild, rightChild;
let swap = null; // 교환할 자식의 인덱스
// 왼쪽 자식이 존재하고, 현재 원소보다 크면 교환 대상으로 지정
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild > element) {
swap = leftChildIndex;
}
}
// 오른쪽 자식이 존재하고, 왼쪽 자식보다 크면 교환 대상으로 지정
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
swap = rightChildIndex;
}
}
if (swap === null) break; // 교환할 대상이 없으면 루프를 종료
// 현재 원소와 교환 대상을 교환
this.heap[index] = this.heap[swap];
this.heap[swap] = element;
index = swap; // 인덱스를 교환된 위치로 업데이트
}
}
// 힙이 비어있는지 확인하는 메서드
isEmpty() {
return this.heap.length === 0;
}
// 최대값(루트)을 반환하는 메서드 (제거하지 않음)
peek() {
return this.heap[0];
}
}
// 2차 시도 (실패) - 힙 알고리즘
// 주어진 연산들을 처리하는 메인 함수
function solution(operations) {
const maxHeap = new MaxHeap(); // 최대 힙
const minHeap = new MaxHeap(); // 최소 힙 (음수로 저장)
let count = 0; // 현재 큐에 있는 원소 수
for (let op of operations) {
const [command, num] = op.split(" ");
if (command === "I") {
// 삽입 연산
maxHeap.push(Number(num));
minHeap.push(-Number(num)); // 최소값을 찾기 위해 음수로 저장
count++;
} else if (count > 0) {
// 삭제 연산 (큐가 비어있지 않을 때만)
if (num === "1") {
maxHeap.pop(); // 최댓값 삭제
count--;
} else {
minHeap.pop(); // 최솟값 삭제
count--;
}
}
}
// 결과 반환
if (count === 0) return [0, 0];
const max = maxHeap.pop();
const min = -minHeap.pop();
return [max, min];
}해당 접근 방식은 최대 힙을 사용하여 문제를 해결하려 했다. 주요 로직은 다음과 같다.
- 최대 힙 두 개를 생성한다. 하나는 최댓값을 관리하고, 다른 하나는 최솟값을 관리한다 (음수로 저장).
- 각 연산을 순회하면서 처리한다.
- I 명령어: 숫자를 두 힙에 모두 추가한다 (최소 힙에는 음수로).
- D 1 명령어: 최대 힙에서 최댓값을 제거한다.
- D -1 명령어: 최소 힙에서 최솟값을 제거한다.
모든 연산을 처리한 후, 각 힙에서 최댓값과 최솟값을 가져와 반환한다.
다만, 이 방법은 힙을 사용하여 삽입과 삭제 연산의 효율성을 높이려 했지만, 두 힙 간의 동기화 문제로 인해 실패했다. 삭제 연산 시 한쪽 힙에서만 값을 삭제하므로, 두 힙의 상태가 일치하지 않게 된다.
시간 복잡도: O(n log n), 여기서 n은 연산의 수다. 각 힙 연산이 O(log n)이기 때문이다.
공간 복잡도: O(n), 여기서 n은 큐에 저장된 원소의 최대 개수다.
3차 시도 (성공)
// MaxHeap 클래스는 2차, 3차 공통
class MaxHeap {
// 최대 힙 자료구조를 구현
constructor() {
this.heap = []; // 힙을 배열로 표현, 루트는 인덱스 0에 위치
}
// 새 원소를 힙에 추가하는 메서드
push(value) {
this.heap.push(value); // 새 원소를 배열의 끝에 추가
this.bubbleUp(); // 새로 추가된 원소를 올바른 위치로 이동
}
// 최대값(루트)을 제거하고 반환하는 메서드
pop() {
if (this.isEmpty()) return null; // 힙이 비어있으면 null을 반환
const max = this.heap[0]; // 최대값은 항상 루트(인덱스 0)에 있음
const end = this.heap.pop(); // 배열의 마지막 원소를 제거
if (this.heap.length > 0) {
this.heap[0] = end; // 마지막 원소를 루트로 이동
this.bubbleDown(); // 루트에서 시작해 올바른 위치로 이동
}
return max; // 최대값을 반환
}
// 새로 추가된 원소를 위로 이동시켜 힙 속성을 유지하는 메서드
bubbleUp() {
let index = this.heap.length - 1; // 새로 추가된 원소의 인덱스
const element = this.heap[index]; // 새로 추가된 원소
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2); // 부모 노드의 인덱스
let parent = this.heap[parentIndex]; // 부모 노드의 값
if (element <= parent) break; // 올바른 위치를 찾으면 루프를 종료
// 부모와 현재 원소를 교환
this.heap[parentIndex] = element;
this.heap[index] = parent;
index = parentIndex; // 인덱스를 부모 인덱스로 업데이트
}
}
// 루트에서 시작해 아래로 이동하며 힙 속성을 유지하는 메서드
bubbleDown() {
let index = 0; // 루트에서 시작
const length = this.heap.length;
const element = this.heap[0]; // 현재 검사 중인 원소
while (true) {
let leftChildIndex = 2 * index + 1; // 왼쪽 자식의 인덱스
let rightChildIndex = 2 * index + 2; // 오른쪽 자식의 인덱스
let leftChild, rightChild;
let swap = null; // 교환할 자식의 인덱스
// 왼쪽 자식이 존재하고, 현재 원소보다 크면 교환 대상으로 지정
if (leftChildIndex < length) {
leftChild = this.heap[leftChildIndex];
if (leftChild > element) {
swap = leftChildIndex;
}
}
// 오른쪽 자식이 존재하고, 왼쪽 자식보다 크면 교환 대상으로 지정
if (rightChildIndex < length) {
rightChild = this.heap[rightChildIndex];
if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild)) {
swap = rightChildIndex;
}
}
if (swap === null) break; // 교환할 대상이 없으면 루프를 종료
// 현재 원소와 교환 대상을 교환
this.heap[index] = this.heap[swap];
this.heap[swap] = element;
index = swap; // 인덱스를 교환된 위치로 업데이트
}
}
// 힙이 비어있는지 확인하는 메서드
isEmpty() {
return this.heap.length === 0;
}
// 최대값(루트)을 반환하는 메서드 (제거하지 않음)
peek() {
return this.heap[0];
}
}
// 3차 시도 (성공) - 힙 알고리즘
// 주어진 연산들을 처리하는 메인 함수
function solution(operations) {
const maxHeap = new MaxHeap(); // 최대 힙 인스턴스 생성
const minHeap = new MaxHeap(); // 최소 힙으로 사용할 최대 힙 인스턴스 생성
let count = 0; // 현재 큐에 있는 원소 수를 추적
// 각 연산을 순회하며 처리
for (let op of operations) {
const [command, num] = op.split(" "); // 연산을 명령어와 숫자로 분리
if (command === "I") {
// 삽입 연산
maxHeap.push(Number(num)); // 최대 힙에 숫자 추가
minHeap.push(-Number(num)); // 최소 힙에는 음수로 추가 (최대 힙을 최소 힙처럼 사용)
count++; // 원소 개수 증가
} else if (count > 0) {
// 삭제 연산 (큐가 비어있지 않을 때만)
if (num === "1") {
maxHeap.pop(); // 최댓값 삭제
} else {
minHeap.pop(); // 최솟값 삭제 (실제로는 최대 힙에서 최대값 삭제)
}
count--; // 원소 개수 감소
// 큐가 비어있으면 두 힙을 초기화 (동기화 유지)
if (count === 0) {
maxHeap.heap = [];
minHeap.heap = [];
}
}
}
// 두 힙 동기화 (불일치하는 원소 제거)
while (count > 0 && -minHeap.peek() > maxHeap.peek()) {
maxHeap.pop();
minHeap.pop();
count--;
}
// 결과 반환
if (count === 0) return [0, 0]; // 큐가 비어있으면 [0, 0] 반환
return [maxHeap.peek(), -minHeap.peek()]; // [최댓값, 최솟값] 반환
}이 접근 방식은 이전의 힙 알고리즘을 개선하여 문제를 해결한다.
- MaxHeap 클래스 구현
- 배열을 사용하여 힙을 표현한다.
- push 메서드: 새 원소를 추가하고 bubbleUp을 호출한다.
- pop 메서드: 최대값(루트)을 제거하고 마지막 원소를 루트로 옮긴 후 bubbleDown을 호출한다.
- bubbleUp: 새로 추가된 원소를 올바른 위치로 이동시킨다.
- bubbleDown: 루트에서 시작해 원소를 올바른 위치로 이동시킨다.
- solution 함수 구현
- maxHeap과 minHeap 두 개의 MaxHeap 인스턴스를 생성한다.
- 각 연산을 순회하며 처리한다:
- 삽입 연산 (I 숫자): 두 힙에 숫자를 추가한다 (minHeap에는 음수로).
- maxHeap.push(Number(num))로 최대 힙에 숫자를 추가
- minHeap.push(-Number(num))로 최소 힙에 숫자의 음수 값을 추가
- 최댓값 삭제 (D 1): maxHeap에서 최댓값을 제거한다.
- maxHeap.pop()으로 최대 힙에서 최댓값을 제거
- 최솟값 삭제 (D -1): minHeap에서 최댓값을 제거한다 (실제로는 최솟값).
- minHeap.pop()으로 최소 힙에서 최솟값을 제거
- 삽입 연산 (I 숫자): 두 힙에 숫자를 추가한다 (minHeap에는 음수로).
- 큐가 비어있을 때마다 두 힙을 초기화하여 동기화를 유지한다.
- 모든 연산 처리 후, 두 힙을 동기화하고 결과를 반환한다.
이 방법은 힙을 사용하여 효율적인 삽입과 삭제를 구현하면서, 동시에 두 힙 간의 동기화 문제를 해결했다.
시간 복잡도: O(n log n), 여기서 n은 연산의 수다. 각 힙 연산이 O(log n)이며, 최종 동기화 과정도 최악의 경우 O(n log n)이다.
공간 복잡도: O(n), 여기서 n은 큐에 저장된 원소의 최대 개수다.
사용한 메서드
- push(): 힙에 새 원소를 추가하고 힙 속성을 유지한다.
- pop(): 힙에서 최대값을 제거하고 반환하며, 힙 속성을 유지한다.
- peek(): 힙의 최대값을 반환한다 (제거하지 않음).
- bubbleUp(): 새로 추가된 원소를 올바른 위치로 이동시킨다.
- bubbleDown(): 루트에서 시작해 원소를 올바른 위치로 이동시킨다.
'💻 종합 개발 주제 > ⌨️ 코딩 테스트' 카테고리의 다른 글
| [프로그래머스] JavaScript Lv1 - 약수의 합(12928) (1) | 2024.07.11 |
|---|---|
| [프로그래머스] JavaScript Lv2 - 최댓값과 최솟값(12939) (0) | 2024.07.11 |
| [프로그래머스] JavaScript Lv2 - 게임 맵 최단거리(1844) (0) | 2024.06.26 |
| [프로그래머스] JavaScript Lv2 - 타겟 넘버(43165) (0) | 2024.06.26 |
| [프로그래머스] JavaScript Lv2 - 큰 수 만들기(42883) (0) | 2024.06.26 |
