0부터 n-1까지의 숫자로 이루어진 배열이 있다고 가정해 봅시다. 이때 어떤 숫자는 여러 번 중복해서 나타날 수 있으며, 우리는 추가 메모리 공간을 전혀 사용하지 않고 이러한 중복된 숫자들을 찾아야 합니다.
예를 들어 n = 7이고 배열이 [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]와 같다면, 중복된 값은 5, 2, 3입니다.
알고리즘 접근 방식
이 문제는 배열 원소의 부호(sign)를 활용하는 영리한 기법으로 해결할 수 있습니다. 모든 값이 0부터 n-1 범위 안에 존재하므로 각 값 자체가 유효한 인덱스 역할을 하며, 해당 인덱스 위치의 값을 음수로 바꾸는 것으로 '이미 방문했음'을 표시할 수 있습니다.
- 배열의 각 원소 e에 대해 다음 단계를 수행합니다.
- sign := A[|e|] — 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
동작 원리
이 알고리즘이 작동하는 핵심 원리는 다음과 같습니다.
- 모든 값이 0부터 n-1 범위 내에 있으므로, 각 값은 곧바로 배열의 유효한 인덱스로 사용될 수 있습니다.
- 값 v를 처음 만나면 arr[v]를 음수로 만들어 'v를 한 번 봤다'는 정보를 기록합니다.
- 이후 동일한 값 v를 다시 만나면 arr[v]가 이미 음수이므로, v가 중복임을 즉시 알 수 있습니다.
- abs() 함수를 사용하는 이유는, 앞선 단계에서 음수로 변경된 값으로 인해 잘못된 인덱스에 접근하는 것을 방지하기 위함입니다.
복잡도 분석
- 시간 복잡도: O(n) — 배열을 딱 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 입력 배열 자체를 수정하여 방문 여부를 저장하므로, 별도의 추가 공간이 전혀 필요하지 않습니다.
다만 이 방법은 원본 배열의 부호가 변경된다는 점에 유의해야 합니다. 원본 데이터를 그대로 유지해야 하는 상황이라면, 처리가 끝난 후 절댓값을 다시 적용해 원래 상태로 복원할 수 있습니다.