개요
코딩테스트에서 자주 등장하는 문제 중 하나는 주어진 수를 정렬하는 것입니다.
본 강좌에서는 JavaScript로 수를 정렬하는 방법에 대해 알아보겠습니다.
수 정렬하기 문제는 기본적인 정렬 알고리즘을 공부하는 데 매우 유용합니다.
우리는 여러 가지 알고리즘을 이용해 수를 정렬할 수 있으며, 각각의 알고리즘은
시간 복잡도와 공간 복잡도가 다릅니다.
문제 설명
문제
주어진 수의 배열을 입력으로 받아서, 정렬된 배열을 반환하는 함수를 작성하시오.
예를 들어, 입력 배열이 [3, 1, 2]이라면,
출력은 [1, 2, 3]이어야 합니다.
입력
- 첫 번째 줄에 정수
N이 주어진다. (1 ≤ N ≤ 100,000) - 두 번째 줄에
N개의 정수A1, A2, ..., AN이 하나의 공백으로 구분되어 주어진다.
(-1,000,000 ≤ Ai ≤ 1,000,000)
출력
정렬된 수를 한 줄에 출력해야 하며, 각 수는 하나의 공백으로 구분되어야 한다.
예제
입력:
5
5 4 3 2 1
출력:
1 2 3 4 5
문제 해결 과정
1단계: 요구사항 분석
주어진 문제를 해결하기 위해서는 입력받은 배열을 정렬하여
출력하는 것이 목표입니다. 이를 위해 우리는 클래식한 정렬 알고리즘인
퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)을 사용할 수 있습니다.
JavaScript 내장 함수를 사용할 수도 있지만, 이번에는 알고리즘을 이해하기 위해
직접 구현해보는 것이 중요합니다.
2단계: 알고리즘 선택
정렬 알고리즘 중 퀵 정렬과 병합 정렬은 일반적으로 고속 정렬 알고리즘으로 널리 사용됩니다.
아래에서 각 알고리즘의 장단점을 간단히 정리하겠습니다.
퀵 정렬(Quick Sort)
- 평균 시간 복잡도:
O(N log N) - 최악 시간 복잡도:
O(N2)(비효율적인 피벗 선택 시) - 공간 복잡도:
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(" "));
결론
이번 강좌에서는 자바스크립트를 이용하여 주어진 수 배열을 정렬하는
문제를 해결했습니다. 정렬 알고리즘의 구현뿐만 아니라,
각 알고리즘의 특징 및 성능에 대해서도 알아보았습니다.
퀵 정렬과 병합 정렬을 직접 구현함으로써 정렬 알고리즘에 대한
이해를 깊게 할 수 있었습니다.
코딩테스트에서는 정렬 문제 외에도 다양한 문제들이 출제되니,
이러한 알고리즘들을 다양하게 연습해보는 것을 추천합니다.
문제 해결 및 연습
아래의 문제들을 풀어보며, 더 많은 연습을 해보세요!
- 주어진 수 배열에서 중복된 수를 제거한 후 정렬하기
- 구간 정렬: 주어진 구간 내에서만 정렬하기
- 정렬된 두 배열을 합치는 문제