문제 설명
서로 다른 6개의 숫자가 들어 있는 리스트가 있다고 가정해 보겠습니다. 이 중 하나의 숫자만 다섯 번 반복되므로, 배열에는 총 10개의 요소가 존재합니다. 목표는 단 두 번의 비교만으로 이 중복 숫자를 찾는 것입니다.
예를 들어 리스트가 [1, 2, 3, 4, 4, 4, 4, 4, 5, 6]과 같다면, 출력 결과는 4가 되어야 합니다.
접근 방법
핵심은 비둘기집 원리(pigeonhole principle)에 있습니다. 배열이 정렬되어 있고 크기가 10일 때, 어떤 숫자가 다섯 번 반복되더라도 해당 숫자들은 반드시 인덱스 3부터 5 사이에 위치하게 됩니다.
따라서 인덱스 3, 4, 5에 있는 값들만 서로 비교하면 중복 숫자를 손쉽게 찾을 수 있습니다.
- array[3] == array[4]라면 → array[3]이 중복 숫자
- array[4] == array[5]라면 → array[4]가 중복 숫자
- 두 조건 모두 거짓이라면 → array[5]가 중복 숫자
세 경우 중 하나는 반드시 참이 되므로, 두 번의 비교만으로 항상 정답을 구할 수 있습니다.
예제 코드
#include<iostream>
using namespace std;
int getDuplicate(int array[]) {
if (array[3] == array[4])
return array[3];
else if (array[4] == array[5])
return array[4];
else
return array[5];
}
int main() {
int a[] = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6};
cout << "Duplicate element: " << getDuplicate(a);
}
실행 결과
Duplicate element: 4
정리
이 방법은 배열이 정렬되어 있고 하나의 숫자가 정확히 다섯 번 나타난다는 전제 조건이 필요하지만, 시간 복잡도 O(1)로 상수 번의 비교만으로 문제를 해결할 수 있다는 점에서 매우 효율적입니다.