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

개요

코딩테스트에서 자주 등장하는 문제 중 하나는 주어진 수를 정렬하는 것입니다.
본 강좌에서는 JavaScript로 수를 정렬하는 방법에 대해 알아보겠습니다.
수 정렬하기 문제는 기본적인 정렬 알고리즘을 공부하는 데 매우 유용합니다.
우리는 여러 가지 알고리즘을 이용해 수를 정렬할 수 있으며, 각각의 알고리즘은
시간 복잡도와 공간 복잡도가 다릅니다.

문제 설명

문제

주어진 수의 배열을 입력으로 받아서, 정렬된 배열을 반환하는 함수를 작성하시오.
예를 들어, 입력 배열이 [3, 1, 2]이라면,
출력은 [1, 2, 3]이어야 합니다.

입력

첫 번째 줄에 정수 N 이 주어진다. (1 ≤ N ≤ 100,000)
두 번째 줄에 N개의 정수 A₁, A₂, ..., A_N이 하나의 공백으로 구분되어 주어진다.
(-1,000,000 ≤ A_i ≤ 1,000,000)

출력

정렬된 수를 한 줄에 출력해야 하며, 각 수는 하나의 공백으로 구분되어야 한다.

예제

문제 해결 과정

1단계: 요구사항 분석

주어진 문제를 해결하기 위해서는 입력받은 배열을 정렬하여
출력하는 것이 목표입니다. 이를 위해 우리는 클래식한 정렬 알고리즘인
퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)을 사용할 수 있습니다.
JavaScript 내장 함수를 사용할 수도 있지만, 이번에는 알고리즘을 이해하기 위해
직접 구현해보는 것이 중요합니다.

2단계: 알고리즘 선택

정렬 알고리즘 중 퀵 정렬과 병합 정렬은 일반적으로 고속 정렬 알고리즘으로 널리 사용됩니다.
아래에서 각 알고리즘의 장단점을 간단히 정리하겠습니다.

퀵 정렬(Quick Sort)

평균 시간 복잡도: O(N log N)
최악 시간 복잡도: O(N²) (비효율적인 피벗 선택 시)
공간 복잡도: O(log N)
장점: in-place 정렬이 가능하여 메모리 사용이 적다.
단점: 안정적인 정렬이 아니다.

병합 정렬(Merge Sort)

평균 및 최악 시간 복잡도: O(N log N)
공간 복잡도: O(N)
장점: 안정적인 정렬이다.
단점: 추가적인 메모리가 필요하다.

3단계: 퀵 정렬 구현

우리는 퀵 정렬을 이용하여 수 배열을 정렬하는 함수를 구현할 것입니다.
아래는 JavaScript로 작성된 퀵 정렬의 구현 코드입니다.


    function quickSort(arr) {
        if (arr.length <= 1) return arr;
        const pivot = arr[arr.length - 1];
        const left = [];
        const right = [];
        
        for (let i = 0; i < arr.length - 1; i++) {
            if (arr[i] < pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return [...quickSort(left), pivot, ...quickSort(right)];
    }

4단계: 병합 정렬 구현

다음으로, 병합 정렬 알고리즘을 구현해보겠습니다. 아래에 병합 정렬의 구현 코드를 제공합니다.


    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, 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));
    }

5단계: 입력 처리 및 출력

이제 정렬 함수들을 완성했으므로, 입력을 처리하고
결과를 출력하는 부분을 구현하겠습니다. JavaScript에서는
prompt를 사용하여 입력을 받을 수 있으며,
결과는 console.log를 사용하여 출력합니다.


    const N = parseInt(prompt("정수의 개수를 입력하세요:"));
    const nums = prompt("정수를 입력하세요:").split(" ").map(Number);
    const sorted = quickSort(nums); // 혹은 mergeSort(nums);
    
    console.log(sorted.join(" "));

결론

이번 강좌에서는 자바스크립트를 이용하여 주어진 수 배열을 정렬하는
문제를 해결했습니다. 정렬 알고리즘의 구현뿐만 아니라,
각 알고리즘의 특징 및 성능에 대해서도 알아보았습니다.
퀵 정렬과 병합 정렬을 직접 구현함으로써 정렬 알고리즘에 대한
이해를 깊게 할 수 있었습니다.
코딩테스트에서는 정렬 문제 외에도 다양한 문제들이 출제되니,
이러한 알고리즘들을 다양하게 연습해보는 것을 추천합니다.

문제 해결 및 연습

아래의 문제들을 풀어보며, 더 많은 연습을 해보세요!

주어진 수 배열에서 중복된 수를 제거한 후 정렬하기
구간 정렬: 주어진 구간 내에서만 정렬하기
정렬된 두 배열을 합치는 문제