문제 개요
0부터 n-1 사이의 정수로 이루어진 배열이 있다고 가정해 봅시다. 어떤 숫자든 여러 번 반복해서 나타날 수 있으며, 이때 추가 공간을 사용하지 않고 반복되는 숫자들을 모두 찾아야 합니다.
예를 들어 n = 7이고 배열이 [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]라면, 중복된 숫자는 5, 2, 3입니다.
알고리즘 원리
이 문제의 핵심은 배열의 모든 값이 0부터 n-1 범위 안에 있다는 점입니다. 덕분에 각 값 자체를 배열의 인덱스로 활용할 수 있으며, 별도의 방문 여부 배열이나 해시 테이블 없이도 각 숫자의 등장 여부를 추적할 수 있습니다.
구체적인 동작 방식은 다음과 같습니다.
- 배열의 각 원소 e에 대해 아래 과정을 수행합니다.
- 인덱스 |e| 위치의 값(A[abs(e)])의 부호를 확인합니다.
- 값이 양수라면 아직 해당 숫자가 등장하지 않았다는 의미이므로, 음수로 바꿔 '방문했음'을 표시합니다.
- 값이 이미 음수라면 해당 숫자가 이전에 한 번 등장했다는 의미이므로, 중복으로 판단하고 출력합니다.
C++ 구현 예제
#include<iostream>
#include<cmath>
using namespace std;
void findDuplicates(int arr[], int size) {
for (int i = 0; i < size; i++) {
if (arr[abs(arr[i])] >= 0)
arr[abs(arr[i])] *= -1;
else
cout << abs(arr[i]) << " ";
}
}
int main() {
int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1};
int n = sizeof(arr)/sizeof(arr[0]);
findDuplicates(arr, n);
}
실행 결과
5 2 3 1
복잡도 분석
- 시간 복잡도: O(n) — 배열의 각 원소를 딱 한 번씩만 확인하면 됩니다.
- 공간 복잡도: O(1) — 입력 배열 자체를 수정해 방문 여부를 저장하기 때문에 추가 메모리가 전혀 필요하지 않습니다.
주의 사항
이 기법은 입력 배열의 원래 값을 직접 변경한다는 점에 유의해야 합니다. 따라서 원본 배열을 그대로 유지해야 하는 상황에는 적합하지 않습니다. 또한 배열의 값이 반드시 0부터 n-1 범위 안에 존재해야만 유효한 인덱스로 사용될 수 있으므로, 범위를 벗어나는 값이 포함된 경우에는 다른 접근 방식을 고려해야 합니다.