[Node.js]백준 24060: 알고리즘 수업 - 병합 정렬 1

백준 알고리즘 재귀단계 - 24060 문제

백준 선생님께서 서준이 아빠 어쩌고 하면서 쉬운 척하면서 어려운 문제를 내주셨다.
병합 정렬에 대한 개념은 알고 있었는데 K 번째 저장..? 의사 코드는 또 뭔 말인지 못알아 듣게 적어주셨다. 문제를 이해하는데도 시간이 오래 걸렸던 문제였다.

풀이 방법

count라는 변수를 0으로 선언하고 merge 함수에서 새 배열에 숫자가 추가될 때마다 count++처리를 해준 뒤 console에 찍어보니 예제에서 나온 총 저장 횟수 12가 출력되었다.

문제에서 요구하는 내용은 K 번째 저장되는 수이므로 count가 K와 같을 때 result 배열에 추가될 값을 target이라는 변수에 할당해주었다.

target이 undefined라면 K가 저장 횟수보다 큰 경우 이므로 -1을 할당해 주었다.

풀이 코드

let fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

let input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.split(" ").map((v) => +v));

const [[N, K], arr] = input;

// N = arr.length
// K -> 배열 merge과정에서 K번째 저장되는 수를 구해야 함.

const merge = (arr1, arr2) => {
  let result = [];
  let [i, j] = [0, 0];

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
    count++;
    if (count === K) target = result[result.length - 1];
  }

  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
    count++;
    if (count === K) target = result[result.length - 1];
  }

  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
    count++;
    if (count === K) target = result[result.length - 1];
  }
  return result;
};

let count = 0;
let target;
const mergeSort = (arr) => {
  if (arr.length <= 1) return arr;
  let mid = Math.ceil(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid));
  let right = mergeSort(arr.slice(mid));
  return merge(left, right);
};

mergeSort(arr);
if (!target) target = -1;
console.log(target);