이 글에서는 첫 번째 인수로 정렬된 숫자 배열, 두 번째 인수로 단일 숫자를 받아, 해당 숫자를 기존 정렬 순서를 유지한 채 배열에 삽입하는 자바스크립트 함수를 작성하는 방법을 소개합니다.
여기서 중요한 제약 조건은 두 가지입니다.
- 숫자를 삽입한 후에도 배열 요소들이 오름차순으로 정렬된 상태를 유지해야 합니다.
- 새로운 배열을 추가로 생성하지 않고 기존 배열에서 직접(in-place) 작업해야 합니다.
접근 방식: 이진 탐색 + 제자리 삽입
삽입할 위치를 찾을 때 선형 탐색 대신 이진 탐색(Binary Search)을 사용하면 위치 탐색 비용을 O(log n)으로 크게 줄일 수 있습니다. 이진 탐색으로 숫자가 들어가야 할 인덱스(왼쪽 경계, lower bound)를 찾은 뒤, 그 위치부터 배열 끝까지 요소들을 한 칸씩 뒤로 밀어내고 해당 자리에 숫자를 넣으면 됩니다.
아래 예제에서는 임시 변수를 하나도 사용하지 않고 덧셈과 뺄셈만으로 두 값을 교환(swap)하는 기법도 함께 활용했습니다.
예제 코드
const arr = [6, 7, 8, 9, 12, 14, 16, 17, 19, 20, 22];
const num = 15;
// val이 삽입되어야 할 가장 왼쪽 인덱스를 이진 탐색으로 찾음
const findIndex = (arr, val) => {
let low = 0, high = arr.length;
while (low < high) {
let mid = (low + high) >>> 1;
if (arr[mid] < val) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
};
// 찾은 위치부터 끝까지 값을 교환하며 뒤로 밀고, 마지막에 num을 push
const insertAt = (arr = [], num) => {
const position = findIndex(arr, num);
for (let i = position; typeof arr[i] !== 'undefined'; i++) {
// 세 번째 변수 없이 값 교환
num += arr[i];
arr[i] = num - arr[i];
num -= arr[i];
}
arr.push(num);
};
insertAt(arr, num);
console.log(arr);
출력 결과
[ 6, 7, 8, 9, 12, 14, 15, 16, 17, 19, 20, 22 ]
숫자 15가 14와 16 사이, 즉 정렬 순서가 깨지지 않는 올바른 위치에 삽입된 것을 확인할 수 있습니다.
코드 동작 원리
1. findIndex — 삽입 위치 찾기
findIndex는 이진 탐색을 수행하여 val보다 크거나 같은 값이 처음 등장하는 인덱스를 반환합니다. 이 위치가 곧 새 숫자가 들어가야 할 자리입니다. (low + high) >>> 1은 비트 연산으로 중간 인덱스를 구하는 부분으로, 부호 없는 오른쪽 시프트(>>>)를 사용해 항상 0 이상의 정수를 얻습니다.
2. insertAt — 제자리 교환으로 요소 밀어내기
insertAt은 찾은 position부터 배열 끝까지 순회하면서 현재 num과 배열 요소의 값을 서로 맞바꿉니다. 일반적으로 값 교환에는 임시 변수가 필요하지만, 여기서는 산술 연산만으로 교환했습니다.
num += arr[i]: 두 값을 합산arr[i] = num - arr[i]: 원래num의 값을 배열에 저장num -= arr[i]: 원래 배열 요소의 값을num에 저장
순회가 끝나면 num에는 배열의 마지막 값이 남아 있으므로, push()로 배열 맨 뒤에 추가하면 삽입이 완료됩니다.
복잡도 분석
- 시간 복잡도: 이진 탐색 O(log n) + 요소 이동 O(n) → 전체 O(n)
- 공간 복잡도: 새 배열을 만들지 않으므로 O(1)
배열의 특성상 중간에 삽입하려면 뒤쪽 요소들을 이동해야 하므로 전체 시간 복잡도는 O(n)이지만, 위치 탐색 자체는 이진 탐색 덕분에 매우 효율적으로 처리됩니다.