N번째 큰수
📚 문제 설명
N 이라는 숫자, N * N 크기의 랜덤한 값들이 저장되어 있는 행렬이 주어진다.
여기서 행렬에 각각의 열에는 숫자가 오름차순으로 되어있다.
해당 행렬에서 N 번째로 큰 숫자를 찾는 문제이다.
예시
-입력-
5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49
-크기순-
52, 49, 48, 41, 35 .......
^ N번째 수
-출력-
35👨🏻💻 풀이 과정
해당 문제를 보고 가장 먼저 든 생각은 행렬을 우선순위큐를 이용하여 저장하는 방식이다.
- 최소 힙을 이용해 오름차순으로 저장되는 우선 순위 큐
MinHeap를 생성한다. MinHeap에 행렬의 값을 저장한다.MinHeap의 크기가N을 넘어가면MinHeap상단 제거
- 행렬의 모든 값을 저장했으면
MinHeap의 최상단 출력MinHeap의 크기가N이기 때문에 힙의 최상단이N번째로 큰 수이다.
메인 로직
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let N = parseInt(input.shift());
input = input.map(v => v.split(' ').map(Number));
class MinHeap {
//생략
}
const minHeap = new MinHeap();
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
// 행렬의 모든 값 Push
// 하지만 minHeap의 크기가 N을 넘지 못하게 유지
minHeap.Push(input[i][j]);
if (minHeap.getSize() > N) minHeap.remove();
}
}
console.log(minHeap.remove());
우선순위 큐 구현에 관한 자세한 설명은 이전 포스트를 참고
전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
let N = parseInt(input.shift());
input = input.map(v => v.split(' ').map(Number));
class MinHeap {
constructor() {
this.heap = [null];
}
// 끝에서부터 계산하여 부모 노드로 올라옴
Push(item) {
let cur = this.heap.length;
while (cur > 1) {
let parent = Math.floor(cur / 2);
if (item < this.heap[parent]) {
this.heap[cur] = this.heap[parent];
cur = parent;
} else break;
}
this.heap[cur] = item;
}
remove() {
const removeItem = this.heap[1];
if (this.heap.length > 2) {
this.heap[1] = this.heap[this.heap.length - 1];
this.heap.pop();
let cur = 1;
let leftChild = cur * 2;
let rightChild = cur * 2 + 1;
// 자식 노드가 있다면 while문 진행
while (this.heap[leftChild]) {
// 왼쪽 자식 노드와 비교할지 오른쪽 자식과 비교할지 선택하는 과정
let CompareChild = leftChild;
if (this.heap[rightChild]) {
if (this.heap[leftChild] > this.heap[rightChild]) {
CompareChild = rightChild;
}
}
// 비교할 자식과 현재 노드를 비교
if (this.heap[CompareChild] < this.heap[cur]) {
// 구조 분해 할당을 이용한 값 교체
[this.heap[CompareChild], this.heap[cur]] = [this.heap[cur], this.heap[CompareChild]];
cur = CompareChild;
}else break;
leftChild = cur * 2;
rightChild = cur * 2 + 1;
}
}else if (this.heap.length === 2) {
this.heap.pop();
} else {
return 0;
}
return removeItem;
}
getSize() {
return this.heap.length - 1;
}
}
const minHeap = new MinHeap();
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
minHeap.Push(input[i][j]);
if (minHeap.getSize() > N) minHeap.remove();
}
}
console.log(minHeap.remove());
이렇게 제출을 했는데 메모리 초과가 나게 되고 도저히 모르겠어서 다른 사람들은 잘통과를 하는지 확인해 보았다.
위의 사진이 Node.js로 필터를 걸고 체점 현황을 확인했을 때 화면이었다.
이게 대체 무슨일이지 하고 검색을 해보니 문제는 입력을 받는 방식의 문제라고 한다.
해당 문제의 경우 readline 모듈을 이용하여 풀지 않으면 다 저렇게 메모리 초과가 난다는 것이다.
그런데 나는 readline 모듈을 잘 몰라서 검색을 해보고 다른 분들의 코드의 입력을 받는 부분을 참고하여 코드를 수정했다.
수정한 코드
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
class MinHeap {
constructor() {
this.heap = [null];
}
Push(item) {
let cur = this.heap.length;
while (cur > 1) {
let parent = Math.floor(cur / 2);
if (item < this.heap[parent]) {
this.heap[cur] = this.heap[parent];
cur = parent;
} else break;
}
this.heap[cur] = item;
}
remove() {
const removeItem = this.heap[1];
if (this.heap.length > 2) {
this.heap[1] = this.heap[this.heap.length - 1];
this.heap.pop();
let cur = 1;
let leftChild = cur * 2;
let rightChild = cur * 2 + 1;
while (this.heap[leftChild]) {
let CompareChild = leftChild;
if (this.heap[rightChild]) {
if (this.heap[leftChild] > this.heap[rightChild]) {
CompareChild = rightChild;
}
}
if (this.heap[CompareChild] < this.heap[cur]) {
[this.heap[CompareChild], this.heap[cur]] = [this.heap[cur], this.heap[CompareChild]];
cur = CompareChild;
}else break;
leftChild = cur * 2;
rightChild = cur * 2 + 1;
}
}else if (this.heap.length === 2) {
this.heap.pop();
} else {
return 0;
}
return removeItem;
}
getSize() {
return this.heap.length - 1;
}
}
const minHeap = new MinHeap();
// 다른 코드를 참조하여 작성
// 입력 받은 줄의 수를 세기 위한 변수
let N = -1;
rl.on("line", function (line) {
// 입력의 첫번째 줄인 행렬의 사이즈를 나타내는 값 저장
if (N === -1) {
N = parseInt(line);
n = N;
return;
}
// 기존 for문과 동일
// minHeap에 행렬 Push 후 길이에 따라 minHeap에서 값 제거
line.split(' ').forEach((value) => {
minHeap.Push(parseInt(value));
if(minHeap.getSize() > n) minHeap.remove();
});
// 한줄이 끝날 때마다 N 감소
N--;
// 만약 모든 줄 다 봤으면 종료
if (N === 0) rl.close();
}).on("close", function () {
console.log(minHeap.remove());
process.exit();
});
이렇게 readline 모듈을 이용하여 입력을 받았더니 무사히 통화할 수 있었다.
🧐 후기
JavaScript에서 우선순위큐를 사용하기 위해 MinHeap을 직접 구현하는 과정을 까먹지 않게 다시 복습을 할 수 있었던 좋은 문제였던 것 같다. 또한 마지막에 입력은 받기 위해 사용하는 readline 모듈에 대해서 검색해보게 되는 좋은 계기를 주는 문제였다.
JavaScript를 사용하는 모두를 위해...