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

문제

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

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, K] = input[0].split(' ').map(Number);
const A = input[1].split(' ').map(Number);

let saveCount = 0;
let result = -1;

function merge_sort(A, p, r) {
    if (p < r) {
        const q = Math.floor((p + r) / 2);
        merge_sort(A, p, q);
        merge_sort(A, q + 1, r);
        merge(A, p, q, r);
    }
}

function merge(A, p, q, r) {
    let i = p;
    let j = q + 1;
    let t = 0;
    const tmp = [];

    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) {
        A[i++] = tmp[t++];
        saveCount++;
        if (saveCount === K) {
            result = A[i - 1];
        }
    }
}

merge_sort(A, 0, N - 1);

console.log(result);

문제 해설

병합 정렬(Merge Sort)을 수행하면서 K번째 저장되는 수를 추적하는 문제입니다. 따라서 주어진 배열을 병합 정렬하면서, 저장되는 수를 카운트하고 K번째에 해당하는 수를 출력하면 됩니다.

 

코드 실행 구조는 아래와 같습니다.

• 병합 정렬의 각 단계에서 배열의 상태가 저장.
• 병합 정렬의 merge 단계에서 배열이 병합되는 과정을 추적하며, 각 저장되는 수를 카운트.
• K번째 저장되는 수를 찾으면 그것을 출력하고, 만약 저장 횟수가 K보다 작다면 -1을 출력.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

각 저장 횟수 추적과 비교는 상수 시간 작업이므로, 전체 시간 복잡도는 𝑂(𝑁 log 𝑁 )이 됩니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

병합 과정에서 임시 배열 tmp가 사용되므로, 추가 공간 복잡도는 𝑂(𝑁)가 됩니다.