오름차순으로 이미 정렬된 정수 배열이 있다고 가정해 봅시다. 이때 자바스크립트 내장 메서드인 Array.prototype.sort()를 사용하지 않고, 아래와 같은 규칙에 따라 배열을 재배열하는 함수를 작성해야 합니다.
- 첫 번째 요소는 최댓값
- 두 번째 요소는 최솟값
- 세 번째 요소는 두 번째로 큰 값
- 네 번째 요소는 두 번째로 작은 값
- 이후에도 같은 방식으로 큰 값과 작은 값을 번갈아 배치
문제 예시
입력 배열이 다음과 같다면,
const arr = [1, 2, 3, 4, 5, 6];
출력 결과는 아래와 같아야 합니다.
const output = [6, 1, 5, 2, 4, 3];
풀이 접근: 투 포인터(Two Pointer) 기법
배열이 이미 오름차순으로 정렬되어 있기 때문에, 별도의 정렬 과정 없이 양쪽 끝에서부터 포인터를 이동시키는 투 포인터 기법으로 문제를 해결할 수 있습니다.
구체적인 동작 순서는 다음과 같습니다.
left포인터는 배열의 시작(최솟값)을,right포인터는 배열의 끝(최댓값)을 가리킵니다.- 먼저
right가 가리키는 값(큰 값)을 결과 배열에 추가합니다. left와right가 서로 다른 위치라면,left가 가리키는 값(작은 값)도 결과 배열에 추가합니다.left는 오른쪽으로,right는 왼쪽으로 한 칸씩 이동합니다.- 결과 배열의 길이가 원본 배열의 길이와 같아질 때까지 반복합니다.
이 방식은 시간 복잡도 O(n), 공간 복잡도 O(n)으로 매우 효율적입니다. 배열이 이미 정렬되어 있다는 전제 조건 덕분에 추가 정렬 없이 한 번의 순회만으로 원하는 결과를 얻을 수 있습니다.
구현 코드
const arr = [1, 2, 3, 4, 5, 6];
const alternativeSort = (arr = []) => {
const res = [];
let left = 0;
let right = arr.length - 1;
while (res.length < arr.length) {
// 큰 값부터 추가
res.push(arr[right]);
// left와 right가 같지 않을 때만 작은 값 추가 (중복 방지)
if (left !== right) {
res.push(arr[left]);
}
left++;
right--;
}
return res;
};
console.log(alternativeSort(arr));실행 결과
위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.
[ 6, 1, 5, 2, 4, 3 ]
핵심 포인트 정리
- 전제 조건 활용: 입력 배열이 이미 정렬되어 있으므로 양 끝 요소가 곧 최댓값과 최솟값입니다.
- 중복 처리: 배열 길이가 홀수일 경우 중앙 요소에서
left === right가 되는데, 이 조건 검사 덕분에 같은 요소가 두 번 추가되는 것을 방지할 수 있습니다. - 효율성: 불필요한 정렬 연산 없이 단 한 번의 선형 순회로 해결하므로 O(n) 시간 복잡도를 보장합니다.