이번 편의 결과물: coding-test/06-sorting/에 정렬 기반 풀이 4개와 직접 구현한 병합 정렬을 작성해 node --test를 통과시킵니다. · 다루는 개념: Array.prototype.sort의 비교 함수, 병합 정렬 직접 구현, 커스텀 비교자, 정렬 후 탐색 패턴
이 편에서 만드는 파일
coding-test/
└── 06-sorting/
├── 01-kth-number-in-range/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 02-unfinished-runner/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 03-largest-number/
│ ├── solution.js (+)
│ └── solution.test.js (+)
└── 04-merge-sort/
├── solution.js (+)
└── solution.test.js (+)개념 정리
Array.prototype.sort의 기본 동작
비교 함수(compareFn) 없이 sort()를 호출하면 모든 요소를 문자열로 바꾼 뒤 유니코드 코드 포인트 순서로 정렬합니다. 숫자 배열에서는 [10, 2, 1].sort()가 [1, 10, 2]가 되는 함정이 생깁니다. compareFn(a, b)가 음수를 반환하면 a가 앞에, 양수면 b가 앞에, 0이면 원래 순서를 유지합니다(ECMAScript 2019부터 sort는 안정 정렬임이 명세로 보장됩니다).
병합 정렬과 퀵 정렬 원리
| 알고리즘 | 평균 시간 | 최악 시간 | 추가 공간 | 안정성 |
|---|---|---|---|---|
| 병합 정렬 | O(n log n) | O(n log n) | O(n) | 안정 |
| 퀵 정렬 | O(n log n) | O(n²) | O(log n) | 불안정 |
병합 정렬은 배열을 반으로 나누고(divide) 각각 재귀적으로 정렬한 뒤(conquer) 두 정렬된 배열을 순서대로 합칩니다(combine). 나누는 대상이 항상 정확히 절반이라 최악의 경우에도 O(n log n)이 보장됩니다. 퀵 정렬은 기준값(pivot)을 골라 작은 값과 큰 값으로 나누는데, pivot을 잘못 고르면(이미 정렬된 배열에서 항상 끝 값을 고르는 경우 등) 한쪽으로 몰려 O(n²)까지 느려질 수 있습니다.
정렬 후 탐색 패턴
배열을 미리 정렬해두면 인접한 값끼리 비교하거나(문제 2), 특정 조건을 만족하는 경계를 이분 탐색으로 찾는(다음 편) 후속 작업이 쉬워집니다. 정렬 비용 O(n log n)을 먼저 지불하고 그 뒤의 탐색·비교를 단순하게 만드는 트레이드오프입니다.
실습
문제 1. 배열 구간에서 K번째 수 찾기
문제 설명
정수 배열 array와 질의 목록 commands가 주어집니다. 각 질의 [i, j, k]는 array의 i번째부터 j번째까지(1부터 시작, 양 끝 포함)를 잘라 오름차순 정렬했을 때 k번째 수를 의미합니다. 모든 질의의 결과를 배열로 반환합니다.
입출력 예
| array | commands | 반환값 |
|---|---|---|
[1, 5, 2, 6, 3, 7, 4] | [[2, 5, 3], [4, 4, 1], [1, 7, 3]] | [5, 6, 3] |
접근(복잡도)
질의마다 slice(i - 1, j)로 구간을 잘라 복사한 뒤 sort((a, b) => a - b)로 오름차순 정렬하고 k - 1 인덱스 값을 읽습니다. 구간 길이를 m이라 하면 질의 하나의 비용은 O(m log m)이고, 질의가 q개면 전체는 O(q × m log m)입니다.
완성 코드
// coding-test/06-sorting/01-kth-number-in-range/solution.js
export function solution(array, commands) {
return commands.map(([from, to, k]) => {
const sliced = array.slice(from - 1, to);
const sorted = [...sliced].sort((a, b) => a - b);
return sorted[k - 1];
});
}테스트
// coding-test/06-sorting/01-kth-number-in-range/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('여러 질의에 대해 구간을 잘라 정렬한 k번째 값을 구한다', () => {
const result = solution([1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]]);
assert.deepStrictEqual(result, [5, 6, 3]);
});
test('구간 길이가 1이면 k는 항상 1이다', () => {
assert.deepStrictEqual(solution([9, 1, 2], [[2, 2, 1]]), [1]);
});
test('원본 배열은 정렬로 변형되지 않는다', () => {
const array = [3, 1, 2];
solution(array, [[1, 3, 1]]);
assert.deepStrictEqual(array, [3, 1, 2]);
});함정
sort()를 원본 배열에 직접 호출하면 배열이 제자리에서 바뀝니다. slice로 새 배열을 얻어도 다시 스프레드([...sliced])로 한 번 더 복사해두면 원본 array가 다른 질의에도 안전하게 재사용됩니다. 비교 함수 없이 sort()만 쓰면 숫자를 문자열 기준으로 정렬해 잘못된 결과가 나옵니다.
문제 2. 완주하지 못한 선수
문제 설명
마라톤 참가자 명단 participant와 완주자 명단 completion이 주어집니다(동명이인이 있을 수 있습니다). completion은 participant보다 정확히 한 명 적습니다. 완주하지 못한 참가자의 이름을 반환합니다.
입출력 예
| participant | completion | 반환값 |
|---|---|---|
["leo", "kiki", "eden"] | ["eden", "kiki"] | "leo" |
["mislav", "stanko", "mislav", "ana"] | ["stanko", "ana", "mislav"] | "mislav" |
접근(복잡도)
두 배열을 각각 정렬하면 완주하지 못한 한 명을 제외한 나머지는 같은 인덱스에서 이름이 일치합니다. 앞에서부터 나란히 비교하다 처음 어긋나는 지점의 participant 쪽 이름이 답이고, 끝까지 어긋나지 않으면 participant의 마지막 이름이 답입니다. 두 배열을 정렬하는 비용이 지배적이라 전체 시간 복잡도는 O(n log n)입니다.
완성 코드
// coding-test/06-sorting/02-unfinished-runner/solution.js
export function solution(participant, completion) {
const sortedParticipant = [...participant].sort();
const sortedCompletion = [...completion].sort();
for (let i = 0; i < sortedCompletion.length; i += 1) {
if (sortedParticipant[i] !== sortedCompletion[i]) {
return sortedParticipant[i];
}
}
return sortedParticipant.at(-1);
}테스트
// coding-test/06-sorting/02-unfinished-runner/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('완주하지 못한 선수 한 명을 찾는다', () => {
assert.strictEqual(solution(['leo', 'kiki', 'eden'], ['eden', 'kiki']), 'leo');
});
test('동명이인이 있어도 정확히 구분한다', () => {
assert.strictEqual(
solution(['mislav', 'stanko', 'mislav', 'ana'], ['stanko', 'ana', 'mislav']),
'mislav',
);
});
test('완주하지 못한 선수가 이름 순으로 가장 마지막이어도 찾는다', () => {
assert.strictEqual(solution(['alice', 'bob'], ['alice']), 'bob');
});함정
두 배열의 길이가 다르므로 반드시 더 짧은 completion 길이만큼만 반복해야 배열 범위를 벗어나지 않습니다. participant.length만큼 반복하면 마지막 비교에서 sortedCompletion[i]가 undefined가 되어 우연히 통과할 수는 있지만 의도가 불명확해집니다.
문제 3. 가장 큰 수 만들기
문제 설명
0 이상의 정수가 담긴 배열 numbers의 원소를 모두 이어붙여 만들 수 있는 가장 큰 수를 문자열로 반환합니다.
입출력 예
| numbers | 반환값 |
|---|---|
[6, 10, 2] | "6210" |
[3, 30, 34, 5, 9] | "9534330" |
접근(복잡도)
두 수 a, b를 비교할 때 크기가 아니라 이어붙인 문자열 a + b와 b + a를 비교해 더 큰 쪽이 앞에 오도록 정렬합니다. 두 문자열의 길이가 항상 같으므로(둘 다 a와 b를 한 번씩 포함) 일반적인 문자열 비교로 정확한 순서를 얻을 수 있습니다. 이 비교자로 정렬한 뒤 이어붙이면 항상 최댓값이 됩니다. 정렬 비용이 지배적이라 전체 시간 복잡도는 O(n log n)입니다.
완성 코드
// coding-test/06-sorting/03-largest-number/solution.js
export function solution(numbers) {
const digits = numbers.map((n) => String(n));
digits.sort((a, b) => {
const ab = a + b;
const ba = b + a;
if (ab === ba) return 0;
return ab > ba ? -1 : 1;
});
if (digits[0] === '0') return '0';
return digits.join('');
}테스트
// coding-test/06-sorting/03-largest-number/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('세 자리 이하 숫자를 조합해 가장 큰 수를 만든다', () => {
assert.strictEqual(solution([6, 10, 2]), '6210');
});
test('자릿수가 다른 숫자들을 올바른 순서로 조합한다', () => {
assert.strictEqual(solution([3, 30, 34, 5, 9]), '9534330');
});
test('모든 원소가 0이면 0 하나만 반환한다', () => {
assert.strictEqual(solution([0, 0]), '0');
});함정
숫자 크기만으로 정렬하면 30과 3처럼 자릿수가 다른 값에서 틀립니다(30이 3보다 크지만 "330"보다 "303"이 더 큰 수입니다). 반드시 이어붙인 문자열끼리 비교해야 합니다. 원소가 모두 0이면 이어붙인 결과가 "00"처럼 앞자리 0이 남을 수 있어 따로 "0"을 반환하도록 처리해야 합니다.
문제 4. 병합 정렬 직접 구현
문제 설명
배열 arr을 병합 정렬(merge sort) 알고리즘으로 오름차순 정렬해 새 배열로 반환하는 solution 함수를 라이브러리 없이 직접 구현합니다. 원본 배열은 바꾸지 않습니다.
입출력 예
| arr | 반환값 |
|---|---|
[5, 2, 4, 6, 1, 3] | [1, 2, 3, 4, 5, 6] |
[1] | [1] |
[] | [] |
접근(복잡도)
배열을 반으로 나눠 각각 재귀적으로 정렬한 뒤, 정렬된 두 배열을 앞에서부터 비교하며 하나로 합칩니다. 나누는 데 O(log n)단계이고 단계마다 병합에 전체 O(n)이 걸려 총 시간 복잡도는 O(n log n)이며, 병합 결과를 담을 배열이 필요해 공간 복잡도는 O(n)입니다. 값이 같을 때 왼쪽 원소를 먼저 넣으면 원래 순서가 유지되는 안정 정렬이 됩니다.
완성 코드
// coding-test/06-sorting/04-merge-sort/solution.js
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 += 1;
} else {
result.push(right[j]);
j += 1;
}
}
return [...result, ...left.slice(i), ...right.slice(j)];
}
export function solution(arr) {
if (arr.length <= 1) return [...arr];
const mid = Math.floor(arr.length / 2);
const left = solution(arr.slice(0, mid));
const right = solution(arr.slice(mid));
return merge(left, right);
}테스트
// coding-test/06-sorting/04-merge-sort/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('섞인 배열을 오름차순으로 정렬한다', () => {
assert.deepStrictEqual(solution([5, 2, 4, 6, 1, 3]), [1, 2, 3, 4, 5, 6]);
});
test('원소가 하나면 그대로 반환한다', () => {
assert.deepStrictEqual(solution([1]), [1]);
});
test('빈 배열은 빈 배열로 반환한다', () => {
assert.deepStrictEqual(solution([]), []);
});
test('원본 배열은 변경되지 않는다', () => {
const original = [3, 1, 2];
solution(original);
assert.deepStrictEqual(original, [3, 1, 2]);
});함정
재귀 종료 조건(arr.length <= 1)을 빠뜨리면 무한 재귀에 빠집니다. merge에서 두 값이 같을 때 left[i] <= right[j] 조건으로 왼쪽을 먼저 넣어야 안정 정렬이 유지됩니다. slice로 원본을 매 단계 복사하므로 추가 메모리가 O(n)만큼 필요합니다.
직접 해보기
- 퀵 정렬을 마지막 원소를 pivot으로 선택하는 방식으로 직접 구현하고, 이미 정렬된 배열
[1, 2, 3, 4, 5]를 입력했을 때left와right가 어떻게 나뉘는지 관찰합니다(최악 케이스 체감). - 문제 1의
solution을 매 질의마다 정렬하지 않고 개선할 수 있는지 생각해봅니다(힌트: 질의 구간이 매번 달라 전체를 한 번만 정렬해두는 방식으로는 대체할 수 없습니다).
정답 보기(1번)
function quickSort(arr) {
if (arr.length <= 1) return [...arr];
const pivot = arr.at(-1);
const rest = arr.slice(0, -1);
const left = rest.filter((n) => n <= pivot);
const right = rest.filter((n) => n > pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}이미 정렬된 배열에서는 매번 pivot이 가장 큰 값이 되어 left에 나머지 전체가 몰리고 right는 항상 빈 배열이 됩니다. 재귀 깊이가 배열 길이만큼 깊어져 최악의 시간 복잡도 O(n²)가 그대로 드러납니다.
자주 하는 실수
| 증상 | 원인 | 고치는 법 |
|---|---|---|
| 숫자 배열을 정렬했는데 순서가 이상함 | 비교 함수 없이 sort() 호출 → 문자열 기준 정렬 | sort((a, b) => a - b)처럼 비교 함수를 명시 |
sort 호출 후 원본 배열이 바뀌어 다른 로직에 영향 | sort는 제자리(in-place) 정렬 | 정렬 전 [...array]로 복사 |
| 가장 큰 수 만들기에서 두 자리 이상 숫자가 섞이면 틀림 | 숫자 크기로만 비교 | 이어붙인 문자열끼리 비교하는 커스텀 비교자 사용 |
| 병합 정렬이 스택 오버플로로 실패 | 재귀 종료 조건 누락 | 길이가 1 이하일 때 즉시 반환 |