문제 정의
0부터 n-1 범위의 숫자로 이루어진 리스트가 있다고 가정해 봅시다. 어떤 숫자든 여러 번 반복해서 나타날 수 있으며, 우리는 추가 메모리 공간을 거의 사용하지 않고 반복되는 숫자들을 모두 찾아야 합니다.
예를 들어 n = 7이고 리스트가 [5, 2, 3, 5, 1, 6, 2, 3, 4, 5]와 같다면, 답은 5, 2, 3입니다.
핵심 아이디어: 부호 표시(Sign Marking) 기법
이 문제를 풀 수 있는 열쇠는 "모든 값이 인덱스 범위 안에 있다"는 조건입니다. 배열의 각 값을 그대로 인덱스처럼 활용하고, 해당 위치의 값 부호를 방문 여부 표시로 바꾸면 별도의 해시셋이나 불린 배열 없이도 중복을 감지할 수 있습니다.
알고리즘 단계
리스트의 각 원소 e에 대해 다음을 수행합니다.
sign := A[abs(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);
return 0;
}
출력 결과
5 2 3 1
동작 과정 살펴보기
입력 배열 {5, 2, 3, 5, 1, 6, 2, 3, 4, 1}을 단계별로 추적해 보면 다음과 같습니다.
- i=0: 값 5 → arr[5]=6이 양수이므로 -6으로 변경
- i=1: 값 2 → arr[2]=3이 양수이므로 -3으로 변경
- i=2: 값 3 → arr[3]=5가 양수이므로 -5로 변경
- i=3: 값 5 → arr[5]가 이미 -6이므로 5 출력
- i=4: 값 1 → arr[1]=2가 양수이므로 -2로 변경
- i=5: 값 6 → arr[6]=2가 양수이므로 -2로 변경
- i=6: 값 2 → arr[2]가 이미 -3이므로 2 출력
- i=7: 값 3 → arr[3]가 이미 -5이므로 3 출력
- i=8: 값 4 → arr[4]=1이 양수이므로 -1로 변경
- i=9: 값 1 → arr[1]가 이미 -2이므로 1 출력
결과적으로 5, 2, 3, 1이 순서대로 출력됩니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 배열을 딱 한 번만 순회합니다.
- 공간 복잡도: O(1) — 입력 배열 자체를 방문 표시 용도로 재활용하므로 추가 공간이 필요하지 않습니다.
주의할 점
- 이 기법은 입력 배열의 내용을 변경합니다. 원본 배열을 유지해야 한다면 실행 후 부호를 abs()로 되돌리거나 다른 방식을 고려해야 합니다.
- 값 0은 부호가 없기 때문에(-0 == 0) 0이 두 번 이상 나오는 경우에는 이 방법만으로 감지되지 않습니다. 이 경우 n+1 같은 오프셋을 더하는 변형 기법(Set 2)을 사용합니다.
- 배열의 모든 값이 유효한 인덱스 범위(0 ~ n-1) 안에 있어야 한다는 전제 조건이 필요합니다.