[백준 / BOJ] 24060번 알고리즘 수업 - 병합 정렬 1 (Javascript / Node js)

https://www.acmicpc.net/problem/24060

24060번: 알고리즘 수업 - 병합 정렬 1

 

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

 

 

위 문제는 "알고리즘 수업" 이라는 제목에 걸맞게 병합 정렬 알고리즘에 대한 코드가 이미 주어져 있고,

주어진 알고리즘을 이해했는지만을 간단히 판단하려는 것이 출제자의 의도인 듯 보인다.

 

문제 해석

 

먼저 병합 정렬 알고리즘에 대해 이해해보자.

 

병합 정렬 알고리즘이란 정렬 대상 배열을 배열의 길이가 1이 될 때까지 반으로 쪼갠 후

쪼개진 길이 1의 파생 배열들을 다시 병합하는 과정에서 정렬을 수행하는 전형적인 분할 정복 알고리즘이다.

 

병합 정렬

 

병합 정렬 알고리즘은 위 그림과 같이 항상 수열을 반으로 나누어 파생된 왼쪽 수열과 오른쪽 수열이 생성 된다.

그리고 병합은 반대로 이루어지기 때문에 항상 한번의 병합을 진행할 때는 두 개의 파생 배열을 대상으로 진행한다.

 

 

위 내용이 매우 당연한 얘기지만 병합 알고리즘의 가장 핵심적인 내용이다.

 

 

이제 병합할 때 어떤 방식으로 정렬이 이루어지는지 살펴보자.

 

 

가장 먼저 파생 배열인 [ 3 ] 과 [ 2 ] 가 병합되는 과정으로 이해해보자.

 

1. 두 파생 배열을 합친 길이의 빈 배열을 생성한다.

2. 새로 생성된 배열에 두 파생 배열의 가장 첫번째 원소들을 비교하여 더 작은 원소를 queue하여 넣는다.

병합 - 1

 

 

배열들을 쪼갰을 때와 마찬가지로 병합 역시 병합된 배열을 반복해서 다른 병합된 배열과 병합해준다.

 

[병합 - 1] 그림에서 설명했듯이 두 배열의 가장 첫번째 원소들끼리 비교하고, 더 작은 원소를 갖고있는 배열을 queue하여 새로운 배열에 먼저 넣어주면 된다.

 

그리고 만약 두 배열중 하나가 모든 원소를 새 배열로 옮겼다면 나머지 한 배열은 이미 전 단계에서 정렬이 완료된 상태이기 때문에 검사 없이 순서대로 뒤에 삽입해주면 된다.

병합 - 2

 

(좀 더 수월한 이해를 위해 queue를 한다고 표현했지만 실제로는 queue하지 않고 단순히 index 번호를 증ㅍ가시켜주기만 해도 된다.)

 

 

 

마지막 단계의 병합을 보며 확실히 이해해보자.

 

 

여기까지가 병합 정렬에 대한 설명이다.

 

이제 다시 문제로 돌아가서, 문제에서 요구하는 답은 "K 번째 저장 되는 수이다."

 

 

여기서 저장 된다는건 배열을 병합할때 새로 생긴 빈 배열에 원소를 하나 넣는 것을 뜻한다.

 

그러니 입력 받은 K를 전역 변수로 선언한 뒤 병합하는 과정에서 새로 생긴 빈 배열에 원소를 삽입할 때마다 K를 감소시키고, K가 0이 됐을때의 원소를 출력해주면 된다.

 

그리고 병합 정렬이 끝났는데도 K가 0보다 클 경우에는 -1을 출력해주면 되겠다.

 

 

전체 코드

 

  const fs = require("fs");

  const input = fs

    .readFileSync("../input.txt")

    .toString()

    .trim()

    .split("\n")

    .map((item) => item.split(" ").map((item) => Number(item)));

  let k = input[0][1];

  let answer = null;

  input.shift();

  let array = input[0];

  function mergeSort(A, p, r) {

    if (p < r) {

      let q = Math.floor((p + r) / 2);

      mergeSort(A, p, q);

      mergeSort(A, q + 1, r);

      merge(A, p, q, r);

    }

  }

  function merge(A, p, q, r) {

    let tmp = [];

    let i = p,

      j = q + 1,

      t = 0;

    while (i <= q && j <= r) {

      if (A[i] <= A[j]) {

        tmp[t++] = A[i++];

      } else {

        tmp[t++] = A[j++];

      }

    }

    while (i <= q) {

      tmp[t++] = A[i++];

    }

    while (j <= r) {

      tmp[t++] = A[j++];

    }

    i = p;

    t = 0;

    while (i <= r) {

      if (--k == 0) {

        answer = tmp[t];

      }

      A[i++] = tmp[t++];

    }

  }

  mergeSort(array, 0, array.length - 1);

  if (k <= 0) console.log(answer);

  if (k > 0) console.log(-1);