주요 포인트 한눈에 보기
이 문제는 “정렬”이 아니라 “정렬된 두 배열을 빠르게 병합”하는 문제입니다.
sort()로 다시 정렬하면 결과는 맞아도 코딩 테스트에서는 감점 또는 오답이 될 수 있습니다.
투 포인터로 O(N + M)에 합치는 흐름을 이해하는 것이 목표입니다.
문제
오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.
입력 설명
첫 번째 줄에 첫 번째 배열의 크기 N(1 ≤ N ≤ 100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1 ≤ M ≤ 100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
출력 설명
오름차순으로 정렬된 배열을 출력합니다.
입력 예제
3
1 3 5
5
2 3 6 7 9
출력 예제
1 2 3 3 5 6 7 9
내가 푼 방식
두 배열을 합친 뒤 sort()로 다시 정렬하는 방식입니다.
구현은 쉽지만, 이 문제의 의도(정렬된 상태 활용)와는 다릅니다.
function solution(arr1, arr2) {
return [...arr1, ...arr2].sort((a, b) => a - b);
}
console.log(solution([1, 3, 5], [2, 3, 6, 7, 9]));동작: 합치고 정렬합니다. 결과는 맞게 나옵니다.
왜 이 방식이 아닌가
이 문제는 두 배열이 이미 정렬되어 있다는 조건을 줍니다.
즉, 다시 정렬하지 말고 “병합”만 하라는 의미입니다.
sort()는 (N+M)log(N+M)만큼 비교가 생깁니다.
반면 투 포인터 병합은 각 원소를 한 번씩만 보고 끝나서 O(N + M)입니다.
코딩 테스트에서는 이런 차이 때문에 오답 처리되기도 합니다.
정답
투 포인터로 두 배열을 동시에 보면서 작은 값부터 결과에 넣습니다.
function solution(arr1, arr2) {
let answer = [];
let p1 = 0;
let p2 = 0;
while (p1 < arr1.length && p2 < arr2.length) {
if (arr1[p1] <= arr2[p2]) {
answer.push(arr1[p1]);
p1++;
} else {
answer.push(arr2[p2]);
p2++;
}
}
while (p1 < arr1.length) {
answer.push(arr1[p1]);
p1++;
}
while (p2 < arr2.length) {
answer.push(arr2[p2]);
p2++;
}
return answer;
}
console.log(solution([1, 3, 5], [2, 3, 6, 7, 9]));정답 해설
1) arr1[p1]과 arr2[p2]를 비교합니다.
2) 더 작은 값을 결과 배열에 넣습니다.
3) 넣은 쪽 포인터만 1칸 이동합니다.
한쪽 배열이 끝나면, 다른 배열의 남은 값은 이미 정렬되어 있으므로 그대로 이어 붙이면 됩니다.
시간 복잡도는 O(N + M)입니다.
포인터가 뒤로 가지 않아서 각 원소를 최대 한 번만 처리합니다.
예제 디테일
기본 예제
console.log(solution([1, 3, 5], [2, 3, 6, 7, 9]));
// [1, 2, 3, 3, 5, 6, 7, 9]동작: 두 포인터가 왼쪽부터 비교하며 작은 값을 순서대로 넣습니다.
메커니즘: 이미 정렬되어 있으니, 현재 작은 값을 선택해도 전체 순서가 깨지지 않습니다.
실수 포인트: 한쪽 배열이 끝난 뒤 남은 값을 붙이는 코드를 빼먹기 쉽습니다.
응용 예제
console.log(solution([-5, -1, 4, 10], [-3, 0, 0, 7]));
// [-5, -3, -1, 0, 0, 4, 7, 10]동작: 음수와 중복이 있어도 비교 규칙은 동일합니다.
메커니즘: 값의 크기 범위는 상관없고, 정렬되어 있다는 조건만 중요합니다.
실수 포인트: 중복 처리에서 조건을 <로만 두면 결과 순서가 달라 보일 수 있습니다.
보통 <=로 한쪽 기준을 고정해 혼란을 줄입니다.
오류 예제
console.log(solution([3, 1, 5], [2, 6]));
// 입력이 정렬되어 있지 않으면 전제가 깨집니다.동작: 투 포인터는 "뒤에 더 작은 값이 없다"고 가정합니다.
메커니즘: [3, 1, 5]처럼 정렬이 깨져 있으면 비교 선택이 틀어질 수 있습니다.
실수 포인트: 문제에 정렬이 보장되지 않으면 먼저 정렬해야 합니다.
이 문제는 정렬이 보장되므로 그 전제를 그대로 사용합니다.
개선 예제
function solutionFast(arr1, arr2) {
const n = arr1.length;
const m = arr2.length;
const answer = new Array(n + m);
let p1 = 0;
let p2 = 0;
let i = 0;
while (p1 < n && p2 < m) {
if (arr1[p1] <= arr2[p2]) {
answer[i] = arr1[p1];
p1++;
} else {
answer[i] = arr2[p2];
p2++;
}
i++;
}
while (p1 < n) {
answer[i] = arr1[p1];
p1++;
i++;
}
while (p2 < m) {
answer[i] = arr2[p2];
p2++;
i++;
}
return answer;
}동작: 정답 풀이와 같지만, 배열을 미리 만들고 인덱스로 채웁니다.
메커니즘: 데이터가 매우 큰 경우 push()보다 예측 가능한 동작을 기대할 수 있습니다.
실수 포인트: 인덱스 i 증가를 빼먹으면 값이 덮어써지거나 빈칸이 남습니다.
방식 비교 표
| 개념 요약 | 장점 | 단점 | 실무 사례 |
|---|---|---|---|
| 투 포인터로 병합 | O(N+M), 정렬 조건 활용 | 잔여 처리 누락 가능 | 정렬된 로그/타임라인 병합 |
합친 뒤 sort() |
구현이 매우 간단 | O((N+M)log(N+M)) | 작은 데이터 임시 처리 |
선택 기준: 코딩 테스트(정렬 보장)라면 투 포인터가 우선입니다.
입력이 작고 빠르게 끝내야 하는 작업이라면 sort()도 실무에서 선택될 수 있습니다.
FAQ
Q. sort()로 풀면 왜 오답이 될 수 있나요?
이 문제는 "정렬된 상태"를 활용하라는 유형입니다.
다시 정렬하면 의도 미충족으로 처리되거나, 큰 입력에서 시간 제한을 넘길 수 있습니다.
Q. 투 포인터는 언제 떠올리면 되나요?
정렬된 배열/리스트를 두 개 이상 동시에 다루거나, 양쪽 끝(경계)을 움직이는 문제가 나오면 먼저 떠올리면 됩니다.
Q. 한쪽이 끝나면 왜 남은 값을 그대로 붙여도 되나요?
남은 배열은 이미 오름차순입니다.
지금까지 결과에 들어간 값들은 그보다 작거나 같은 값들이므로, 그대로 이어 붙여도 정렬이 유지됩니다.
Q. 시간 복잡도 O(N+M)을 어떻게 설명하면 좋나요?
포인터는 뒤로 가지 않고 끝까지 한 번씩만 이동합니다.
그래서 각 원소를 최대 한 번만 처리하고, 전체 작업량은 두 길이의 합이 됩니다.
Q. 중복 값이 있으면 <=가 꼭 필요한가요?
정렬 결과만 요구한다면 <도 가능하지만, 한쪽 기준을 고정하려면 <=가 더 깔끔합니다.
중복이 많은 입력에서 흐름이 안정적으로 보입니다.
Q. 입력이 정렬되어 있지 않다면 어떻게 해야 하나요?
먼저 정렬한 뒤 병합해야 합니다.
다만 이 문제는 정렬이 보장되므로, 정렬 단계 없이 병합만 하는 것이 정답입니다.