[백준 2075번][Javascript][NodeJS] N번째 큰 수

2075번: N번째 큰 수

2075번: N번째 큰 수

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 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

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 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

예제 출력

35

 

---

풀이

주제를 알지 못했을 때의 플로우

1. 말 그대로 N번째 큰 수를 찾는 것, 각 열이 정렬되어 있다는 조건
2. 각 열에서 끝 행의 숫자들을 비교해가며 찾는 방식은 어떨까?
3. 이렇게도 저렇게도 각 열마다의 숫자가 뒤죽박죽이기때문에 전체의 숫자를 탐색해야 한다
4. 최대 1,500의 N 값이고, 최댓값을 하나씩 뺄 경우에, 다음 최댓값을 알아내는 구조가 필요함
5. 숫자들을 push하고, 최댓값을 pop 할 수 있는 우선순위 큐(Heap)가 적합함을 알 수 있음

주제를 알고서의 플로우

1. N번 째 큰 수를 찾으므로, 전체 수를 최대힙(MaxHeap)에 insert 하고, N번을 pop?
   —> 메모리 초과
   —> 힙의 insert는 힙의 배열 수에 연관된다 (O(N))
   —> 따라서, 힙의 최대 개수를 줄여주는 건 동작에 큰 영향을 미치게 된다
2. N개의 힙의 개수 제한을 둔다고 가정하자
   N번째 큰 수(a)가 힙에 남아있으려면, N개가 넘어갈 때, a보다 작은 수를 빼면 된다
   —> 최소힙을 구현하여, size가 N+1 이 넘어갈 때 pop을 해준다
   —> 전체 수를 insert 하고 나면, a가 최소인 N개의 힙이 남아있게 된다

---

코드 (리뷰 환영)

class MinHeap {
  constructor() {
    this.list = [null];
  }
 
  swap(a, b) {
    [this.list[a], this.list[b]] = [this.list[b], this.list[a]];
  }
 
  getParent(current) {
    return this.list[Math.floor(current / 2)];
  }
 
  getLeftChildIdx(current) {
    return current * 2;
  }
 
  getRightChildIdx(current) {
    return current * 2 + 1;
  }
 
  bubbleUp() {
    let pos = this.size() - 1;
    while (pos >= 1) {
      const parent = this.getParent(pos);
      const parentIdx = Math.floor(pos / 2);
      if (!parent) return;
 
      if (parent > this.list[pos]) {
        this.swap(parentIdx, pos);
        pos = parentIdx;
      } else return;
    }
  }
 
  bubbleDown() {
    let pos = 1;
    while (pos < this.size()) {
      const leftIdx = this.getLeftChildIdx(pos),
        rightIdx = this.getRightChildIdx(pos);
 
      let maxIndex = pos;
      if (leftIdx < this.size() && this.list[leftIdx] < this.list[maxIndex])
        maxIndex = leftIdx;
      if (rightIdx < this.size() && this.list[rightIdx] < this.list[maxIndex])
        maxIndex = rightIdx;
 
      if (maxIndex !== pos) {
        this.swap(maxIndex, pos);
        pos = maxIndex;
      } else return;
    }
  }
 
  insert(element) {
    this.list.push(element);
    this.bubbleUp();
  }
 
  pop() {
    if (this.size() === 2) return this.list.pop();
 
    const answer = this.list[1];
 
    this.list[1] = this.list.pop();
    this.bubbleDown();
 
    return answer;
  }
 
  size() {
    return this.list.length;
  }
 
  empty() {
    return this.size() === 1;
  }
}

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [_N, ...inputs] = fs.readFileSync(filePath).toString().trim().split("\\n");
 
const N = +_N;
 
// -----------------------------------
 
const myQ = new MinHeap();
let answer = -1;
 
const [...nums] = inputs.map((line) => {
  return line.split(" ").map(Number);
});
 
nums.forEach((line) => {
  for (let num of line) {
    myQ.insert(num);
 
    if (myQ.size() > N) answer = myQ.pop();
  }
});
 
// -----------------------------------
 
console.log(answer);

 

여기서 잠깐!

• 사실 해당 코드는 답이 아니다 😲
• 해당 문제는 node JS 에서 풀면 메모리 초과가 거의 나게 되는 문제로,,
  정답인 코드들을 보아도 같은 로직이지만,
  readline 모듈을 사용하는 등으로 통과된 것으로 추정된다
• (readline 모듈로 해보려는데 잘 몰라서 못함,, 아시면 알려주세요)
• JS 코테는 어느 정도까지 나오는 건지🤔🤔