문제 설명
주어진 수 N개를 비내림차순으로 정렬하는 프로그램을 작성하시오. 비내림차순은 정렬된 순서에서 이전 숫자보다 같은 숫자이거나 큰 숫자가 나오는 경우를 의미합니다.
입력
첫째 줄에 수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에 수가 주어진다. 각 수는 정수이고, 절댓값이 1,000,000보다 작거나 같다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬된 수를 하나씩 출력한다.
5
5
2
3
1
4
출력 예시:
1
2
3
4
5
문제 해결 과정
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
결론
이번 문제를 통해 자바스크립트를 활용한 정렬 알고리즘의 중요성과 병합 정렬의 구현 방법을 배울 수 있었습니다.
실전 면접 및 코딩 테스트에서 자주 출제되는 주제인 만큼, 다양한 케이스를 연습하고 구현해 보는 것이 중요합니다.
알고리즘의 이론을 이해하는 것과 함께, 직접 코드를 작성해 보면서 손에 익히는 것이 실력을 향상시키는 중요한 방법입니다.