이 문제에서는 크기가 N인 배열 arr[]가 주어집니다. 배열에는 1부터 N-1까지의 값이 들어 있으며, 단 하나의 값만 두 번 반복하여 나타납니다. 우리의 목표는 크기 n인 정렬된 배열에서 유일한 중복(반복) 요소를 찾는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력
arr[] = {1, 2, 3, 4, 5, 5, 6, 7}출력
5
풀이 접근 방법 1: 선형 탐색
가장 간단한 방법은 선형 탐색(linear search)을 사용하는 것입니다. 배열을 순회하면서 인접한 두 요소 arr[i]와 arr[i+1]의 값을 비교합니다. 두 값이 같다면 그 값이 바로 중복된 값이므로 arr[i]를 반환하면 됩니다.
배열이 정렬되어 있기 때문에 중복 값은 반드시 서로 인접해 있다는 점을 활용한 방식입니다. 시간 복잡도는 O(N)입니다.
예제 1
아래 프로그램은 선형 탐색 기반 해결 방법의 동작을 보여줍니다.
#include <iostream>
using namespace std;
int findRepeatingValueArr(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] == arr[i+1])
return (arr[i]);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 4, 5, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, N);
return 0;
}출력
The repeating value in the array is 4
풀이 접근 방법 2: 이진 탐색
더 효율적인 방법은 이진 탐색(binary search) 알고리즘을 활용하는 것입니다. 핵심 아이디어는 다음과 같습니다.
배열에 1부터 N-1까지의 값이 순서대로 저장되어 있고 중복이 하나뿐이라면, 중복 지점 이전에는 arr[i] == i + 1 관계가 성립하고, 중복 지점 이후에는 이 관계가 깨지게 됩니다.
- 중간(mid) 인덱스에서 arr[mid]가 이미 앞에서 한 번 나타난 값이라면(즉, arr[mid] == arr[mid-1]), 해당 값이 중복 요소이므로 반환합니다.
- 중간 인덱스의 값이 기대값(mid + 1)과 일치한다면, 중복 요소는 오른쪽 부분 배열에 존재하므로 오른쪽을 탐색합니다.
- 일치하지 않는다면 왼쪽 부분 배열을 탐색합니다.
이 방법은 시간 복잡도 O(log N)으로 선형 탐색보다 훨씬 효율적입니다.
예제 2
아래 프로그램은 이진 탐색 기반 해결 방법의 동작을 보여줍니다.
#include <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
if (s > e)
return -1;
int mid = (s + e) / 2;
if (arr[mid] != mid + 1){
if (mid > 0 && arr[mid]==arr[mid-1])
return arr[mid];
return arr[findRepeatingValueArr(arr, s, mid-1)];
}
return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, 0, n-1);;
return 0;
}출력
The repeating value in the array is 6
마무리
정렬된 배열에서 유일한 중복 요소를 찾는 문제는 선형 탐색으로도 해결할 수 있지만, 배열의 정렬 특성과 인덱스-값 관계를 활용한 이진 탐색을 적용하면 O(log N)의 시간 복잡도로 더 빠르게 해결할 수 있습니다. 데이터의 크기가 클수록 이진 탐색 방식이 실질적으로 유리합니다.