자바스크립트 코딩테스트 강좌, 수 정렬하기 1

문제 설명

주어진 수 N개를 비내림차순으로 정렬하는 프로그램을 작성하시오. 비내림차순은 정렬된 순서에서 이전 숫자보다 같은 숫자이거나 큰 숫자가 나오는 경우를 의미합니다.

입력

첫째 줄에 수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. 각 수는 정수이고, 절댓값이 1,000,000보다 작거나 같다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬된 수를 하나씩 출력한다.

문제 해결 과정

1단계: 문제 분석

주어진 문제를 이해하기 위해 입력 데이터의 구조와 요구되는 출력을 분명히 해야 합니다.
– 입력: 수 N과 그 다음 N개의 정수
– 출력: N개의 정수를 비내림차순으로 정렬한 결과

문제의 핵심은 효율적인 정렬 알고리즘을 사용하는 것입니다.
배열의 크기가 최대 1,000,000이기 때문에 일반적인 O(N^2) 알고리즘(버블 정렬, 선택 정렬 등)은 사용할 수 없습니다.
그러므로 O(N log N)의 복잡도를 갖는 정렬 알고리즘인 퀵 정렬, 병합 정렬 등을 사용해야 합니다.

2단계: 알고리즘 선택

자바스크립트의 내장 메소드인 Array.prototype.sort()를 사용할 수 있지만,
정렬의 안정성을 보장해야 하기 때문에 쿼키 정렬이나 병합 정렬을 구현해 볼 것입니다.

3단계: 구현

병합 정렬(Merge Sort) 알고리즘을 사용하여 문제를 해결하겠습니다.
병합 정렬은 리스트를 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 두 정렬된 부분을 합치는 방식으로 동작합니다.

병합 정렬의 실행 과정

• 배열을 반으로 나누어 두 개의 서브 배열로 분할합니다.
• 각 서브 배열을 재귀적으로 정렬합니다.
• 정렬된 두 서브 배열을 합쳐서 하나의 정렬된 배열을 만듭니다.

병합 정렬 구현

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0; 
    let j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] < right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
}
    

4단계: 입력 및 출력 처리

이제 입력을 받고 병합 정렬을 이용하여 정렬한 후, 결과를 출력하는 함수를 작성하겠습니다.
노드를 입력받고 배열로 변환한 후 병합 정렬 함수를 호출하도록 하겠습니다.

const fs = require('fs');

// 입력을 파일에서 읽습니다.
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(Number);
const n = input.shift(); // 첫 번째 줄의 수 개수를 제거합니다.

const sortedArray = mergeSort(input);

console.log(sortedArray.join('\\n')); // 줄 바꿈으로 정렬된 결과를 출력합니다.
    

5단계: 테스트 및 결과 검증

구현된 코드를 테스트하고, 입력 예제를 사용하였습니다.
입력으로 다음을 사용했을 때,

5
5
2
3
1
4
    

예상되는 출력은 다음과 같습니다.

1
2
3
4
5
    

결론

이번 문제를 통해 자바스크립트를 활용한 정렬 알고리즘의 중요성과 병합 정렬의 구현 방법을 배울 수 있었습니다.
실전 면접 및 코딩 테스트에서 자주 출제되는 주제인 만큼, 다양한 케이스를 연습하고 구현해 보는 것이 중요합니다.
알고리즘의 이론을 이해하는 것과 함께, 직접 코드를 작성해 보면서 손에 익히는 것이 실력을 향상시키는 중요한 방법입니다.