정렬된 리터럴 배열이 하나 주어져 있다고 가정해 보겠습니다. 우리가 작성해야 할 함수는 배열 안의 모든 중복 요소를 제거하여 각 요소가 딱 한 번만 나타나도록 만들고, 그 결과 배열의 새로운 길이를 반환하는 역할을 합니다.
단, 여기에는 중요한 제약 조건이 있습니다. 별도의 배열을 위한 추가 공간을 할당할 수 없다는 점입니다. 즉, O(1)의 추가 메모리만 사용하면서 입력 배열 자체를 직접 수정(in-place)하는 방식으로 문제를 해결해야 합니다.
예제 코드
이를 구현한 코드는 다음과 같습니다.
const arr = [1, 3, 3, 6, 7, 7, 9, 11, 13];
const removeDuplicates = (arr = []) => {
let i = 0;
while(i < arr.length - 1){
let j = i + 1;
if(arr[i] === arr[j]){
arr.splice(j, 1);
} else {
i++;
}
};
};
removeDuplicates(arr);
console.log(arr);
출력 결과
콘솔에 출력되는 결과는 다음과 같습니다.
[
1, 3, 6, 7,
9, 11, 13
]
코드 동작 원리
이 알고리즘은 인접한 두 요소를 비교하는 단순한 방식으로 동작합니다.
- 변수
i는 현재 기준이 되는 요소의 위치를 가리킵니다. - 변수
j는i바로 다음 위치를 가리키며,arr[i]와arr[j]의 값을 비교합니다. - 두 값이 같으면
splice()를 호출해j위치의 중복 요소를 배열에서 제거합니다. - 두 값이 다르면
i를 1 증가시켜 기준점을 다음 요소로 옮깁니다. - 배열의 끝에 도달할 때까지 이 과정을 반복하면 모든 중복이 제거됩니다.
성능 개선: 투 포인터(Two-Pointer) 기법
splice()는 요소를 하나 제거할 때마다 그 뒤의 모든 요소를 앞으로 한 칸씩 이동시켜야 하므로 O(n)의 비용이 듭니다. 따라서 위 코드의 전체 시간 복잡도는 최악의 경우 O(n²)가 됩니다.
배열이 이미 정렬되어 있다는 특성을 활용하면 투 포인터(two-pointer) 기법으로 O(n) 시간에 문제를 해결할 수 있습니다. 읽기 포인터와 쓰기 포인터를 두고, 서로 다른 값을 만나는 시점에만 쓰기 포인터 위치에 값을 덮어쓰는 방식입니다.
const removeDuplicatesOptimized = (arr = []) => {
if (arr.length === 0) return 0;
let writeIndex = 0; // 쓰기 포인터
for (let readIndex = 1; readIndex < arr.length; readIndex++) {
if (arr[readIndex] !== arr[writeIndex]) {
writeIndex++;
arr[writeIndex] = arr[readIndex];
}
}
const newLength = writeIndex + 1;
arr.length = newLength; // 뒤쪽 불필요한 부분 잘라내기
return newLength;
};
const nums = [1, 3, 3, 6, 7, 7, 9, 11, 13];
console.log(removeDuplicatesOptimized(nums)); // 7
console.log(nums); // [1, 3, 6, 7, 9, 11, 13]이 방식은 요소 이동 없이 각 요소를 한 번씩만 순회하므로, 대용량 데이터를 다룰 때 훨씬 효율적입니다.
마무리
정렬된 배열에서 중복을 제거하는 문제는 코딩 테스트와 실무에서 자주 등장하는 기본기 문제입니다. 핵심은 배열이 정렬되어 있으므로 중복 요소는 반드시 인접해 있다는 사실을 활용하는 것입니다. 간단한 인접 비교 방식부터 투 포인터 최적화까지, 상황과 데이터 크기에 맞는 방법을 선택해 적용해 보시기 바랍니다.