가운데를 말해요
중간값을 구하는 문제로, 수를 추가할 때마다 매번 sort() 메서드를 통해 중간값을 구하니 메모리 초과가 발생했다. 시간 제한이나 공간 제한이 촉박하다보니 다른 방법을 알아봐야만 했다. 그래서 선택한 방법이 최대힙, 최소힙을 이용한 방법 그리고 이진 탐색을 통해 항상 정렬을 유지하는 방법으로 진행했다.
최대힙, 최소힙으로 문제 해결하기
저번 포스팅에서 최대힙, 최소힙을 직접 구현해보았다. 문제 해결을 위해 다시 작성해보면서 몇 가지를 수정하고 추가했다.
class Heap {
constructor(comparator = (lhs, rhs) => lhs < rhs) {
this.heap = [0];
this._comparator = comparator;
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
empty() {
return this.heap.length === 1;
}
peek() {
return this.heap[1];
}
size() {
return this.heap.length - 1;
}
insert(data) {
this.heap.push(data);
const moveUp = (index = this.heap.length - 1) => {
const parentIndex = Math.floor(index / 2);
if (index === 1 || !this._comparator(this.heap[index], this.heap[parentIndex])) return;
this.swap(index, parentIndex);
moveUp(parentIndex);
};
moveUp();
}
extract() {
if (this.empty()) return;
if (this.size() === 1) return this.heap.pop();
const data = this.heap[1];
this.heap[1] = this.heap.pop();
const moveDown = (index = 1) => {
const leftChildIndex = index * 2;
const rightChildIndex = index * 2 + 1;
if (leftChildIndex >= this.heap.length) return 0;
if (rightChildIndex >= this.heap.length) {
if (this._comparator(this.heap[leftChildIndex], this.heap[index])) {
this.swap(leftChildIndex, index);
moveDown(leftChildIndex);
}
} else {
if (this._comparator(this.heap[leftChildIndex], this.heap[rightChildIndex])) {
if (this._comparator(this.heap[leftChildIndex], this.heap[index])) {
this.swap(leftChildIndex, index);
moveDown(leftChildIndex);
}
} else {
if (this._comparator(this.heap[rightChildIndex], this.heap[index])) {
this.swap(rightChildIndex, index);
moveDown(rightChildIndex);
}
}
}
};
moveDown();
return data;
}
}Heap 생성 시, comparator를 추가해서 최대 힙인 경우, 최소 힙인 경우를 구분할 수 있으므로 이름을 Heap으로 하였다. 크기를 비교하기 위해 size()를 추가하였고, 값을 꺼내오는 것이 아닌 확인만 할 수 있는 peek()을 추가했다.
아래는 문제 해결 코드이다.
// https://www.acmicpc.net/problem/1655
const readline = require("readline");
const reader = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
/**
* 최대힙과 최소힙을 활용하여 중간값을 얻는다.
*
* >> 최대힙의 최댓값이 최소힙의 최솟값보다 항상 작거나 같게 유지를 하면, 최대힙의 최댓값이 항상 중간값이 된다.
*
* [ 1, 5, 2, 10, -99, 7, 5 ]
* 최대힙 최소힙
* 1: [1], [] => 최소힙이 empty라면 최대힙을 중간값으로 한다. (1)
* 5: [1], [5] => 두 사이즈가 같으므로 최대힙의 최대를 중간값으로 한다. (1)
* 2: [2, 1], [5] => 최대힙보다 최소힙이 항상 더 작게 유지해야하므로 2를 최대힙으로 옮긴다. (2)
* 10: [2, 1], [5, 10] => 최대힙의 최대가 최소힙의 최소보다 작으므로 2를 중간값으로 한다.
* -99: [2, 1, -99], [5, 10] => 위와 같다. (2)
* 7: [2, 1, -99], [5, 7, 10] => 위와 같다. (2)
* 5: [5, 2, 1, -99], [5, 7, 10] => 5는 최소힙의 최소와 같으므로 최대힙의 최대가 된다. (5)
*
* @param {number[]} numbers 수빈이가 외치는 정수
* @return 수빈이의 동생이 말해야 하는 수
*/
function solution(numbers) {
const maxHeap = new Heap((lhs, rhs) => lhs > rhs);
const minHeap = new Heap();
return numbers
.map((number) => {
maxHeap.size() === minHeap.size() ? maxHeap.insert(number) : minHeap.insert(number);
if (maxHeap.peek() > minHeap.peek()) {
const temp = minHeap.extract();
minHeap.insert(maxHeap.extract());
maxHeap.insert(temp);
}
console.log(maxHeap.heap, minHeap.heap);
return maxHeap.peek();
})
.join("\n");
}
// ... Declaration of Heap Class
const lines = [];
reader
.on("line", (line) => {
lines.push(line.trim());
})
.on("close", () => {
const N = Number(lines.shift());
const numbers = lines.map(Number);
console.log(solution(numbers));
process.exit();
});
lhs와 rhs의 대소비교를 통해 최대힙과 최소힙을 구분할 수 있다. 기본 매개변수로는 최소 힙으로 구현되어 있다.
const maxHeap = new Heap((lhs, rhs) => lhs > rhs);
const minHeap = new Heap();numbers를 순회하면서 최대힙과 최소힙에 숫자를 추가한다.
차례대로 부를 수: 1 15 5 3 2 -99 7 5
최대힙 & 최소힙: [] []
중간값 {}
# 매번 반복에서 최대 힙의 최댓값이 중간값이 된다.
1. 최대힙과 최소힙의 사이즈가 같으면 최대힙에 숫자 추가, 다르면 최소힙에 숫자 추가
2. 최대힙의 최댓값이 최소힙의 최솟값보다 크다면, 두 값을 스왑한다.
3. 최대힙의 최댓값이 중간값이 되므로 이를 반환한다.
1: {1}
사이즈 같음: [1] []
최소힙 없음
15: {1}
사이즈 다름: [1] [15]
최솟값이 더 큼
5: {5}
사이즈 같음: [5, 1] [15]
최솟값이 더 큼
3: {3}
사이즈 다름: [5, 1] [3, 15]
최댓값이 더 큼: [3, 1] [5, 15]
2: {3}
사이즈 같음: [3, 2, 1] [5, 15]
최솟값이 더 큼
-99: {2}
사이즈 다름: [3, 2, 1] [-99, 5, 15]
최댓값이 더 큼: [2, 1, -99] [3, 5, 15]
7: {3}
사이즈 같음: [7, 2, 1, -99] [3, 5, 15]
최댓값이 더 큼: [3, 2, 1, -99] [5, 7, 15]
5: {3}
사이즈 다름: [3, 2, 1, -99] [5, 5, 7, 15]
최솟값이 더 큼
최종적으로 1 1 5 3 3 2 3 3 가 출력된다.return numbers
.map((number) => {
maxHeap.size() === minHeap.size() ? maxHeap.insert(number) : minHeap.insert(number);
if (maxHeap.peek() > minHeap.peek()) {
const temp = minHeap.extract();
minHeap.insert(maxHeap.extract());
maxHeap.insert(temp);
}
return maxHeap.peek();
})
.join("\n");이진탐색으로 문제 해결하기
이진탐색을 통해 매번 오름차순을 유지하는 방법으로 진행하면 으로 문제를 해결할 수 있다.
// https://www.acmicpc.net/problem/1655
const readline = require("readline");
const reader = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
/**
* 이진탐색을 활용하여 항상 오름차순을 유지한다. 중간값을 출력한다.
* [ 1, 5, 2, 10, -99, 7, 5 ]
*
* [-99, 1, 2, 5, 10] <- 7
*
* left = 0; right = arr.length - 1; mid = Math.floor((left + right) / 2);
* => left = 0;, right = 4; mid = 2;
*
* arr[mid]가 7보다 작으므로 left = mid + 1;
* => left = 3; right = 4; mid = 3
*
* arr[mid]가 7보다 작으므로 left = mid + 1;
* => left = 4; right = 4; mid = 4
*
* arr[mid]가 7과 같으므로 arr.splice(mid, 0, 7)로 배열에 값 추가
*
* @param {number[]} numbers 수빈이가 외치는 정수
* @return 수빈이의 동생이 말해야 하는 수
*/
function solution(numbers) {
const arr = [];
return numbers
.map((number) => {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] <= number) left = mid + 1;
else right = mid - 1;
}
arr.length ? arr.splice(left, 0, number) : arr.push(number);
const mid = Math.floor(arr.length / 2);
if (arr.length % 2) return arr[mid];
return arr[mid - 1];
})
.join("\n");
}
const lines = [];
reader
.on("line", (line) => {
lines.push(line.trim());
})
.on("close", () => {
const N = Number(lines.shift());
const numbers = lines.map(Number);
console.log(solution(numbers));
process.exit();
});배열의 특정 인덱스에 값을 삽입하기 위해서 splice 메서드를 사용했다. 최악의 경우 의 시간복잡도가 필요하다.
아래가 최대힙/최소힙으로 해결한 문제고, 위가 이진탐색으로 해결한 문제이다.
