개념
서로 내용이 거의 같은 두 개의 배열이 주어지고, 단 한 개의 요소만 어느 한쪽 배열에서 빠져 있다고 가정해 봅시다. 이때 우리의 과제는 바로 그 누락된 요소를 찾아내는 것입니다.
입력 예시
arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}출력
2
두 번째 배열에는 2가 빠져 있습니다.
입력 예시
arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}출력
7
첫 번째 배열에는 7이 빠져 있습니다.
해결 방법
1. 선형 탐색 (단순 접근)
가장 간단한 방법은 두 배열을 처음부터 끝까지 순회하면서 요소를 하나씩 비교하고, 일치하지 않는 지점을 발견하면 그 요소를 누락된 요소로 표시하는 것입니다. 하지만 이 방법은 배열 크기에 비례하는 O(n)의 선형 시간이 필요하다는 단점이 있습니다.
2. 이진 탐색 (효율적 접근)
배열이 정렬되어 있다면 이진 탐색을 활용해 O(log n) 시간 안에 누락된 요소를 찾을 수 있습니다. 알고리즘은 다음과 같이 단계별로 진행됩니다.
- 더 큰 배열에서 이진 탐색을 시작하고, 중간 인덱스를
(low + high) / 2로 계산합니다. - 두 배열에서 mid 인덱스의 값이 서로 같다면, 누락된 요소는 반드시 오른쪽 부분에 있으므로
low = mid로 갱신합니다. - 값이 서로 다르다면, 누락된 요소는 왼쪽 부분에 있으므로
high = mid로 갱신합니다. - 배열의 크기가 1이거나 0인 특수한 경우는 별도로 처리해야 합니다. 이때는 해당 단일 요소 자체가 곧 누락된 요소입니다.
또한 첫 번째 요소부터 이미 서로 다르다면, 그 요소가 곧 누락된 요소임을 바로 확인할 수 있습니다.
예제 코드
// 동일한 두 배열(단 하나의 요소만 빠짐)에서
// 누락된 요소를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
// 이진 탐색 기반으로 누락된 요소를 찾는 함수.
// arrA[]는 더 큰 배열이며 Q는 그 크기입니다.
// arrA[]와 arrB[]는 같은 순서로 정렬되어 있다고 가정합니다.
int findMissingUtil(int arrA[], int arrB[], int Q){
// 특수 케이스: 두 번째 배열에서 단 하나의 요소만 빠진 경우
if (Q == 1)
return arrA[0];
// 특수 케이스: 첫 번째 요소가 누락된 경우
if (arrA[0] != arrB[0])
return arrA[0];
// 현재 탐색 범위의 경계 지점 초기화
int low = 0, high = Q - 1;
// low < high인 동안 반복
while (low < high){
int mid = (low + high) / 2;
// mid 인덱스의 요소가 서로 같다면
// 오른쪽 부분 배열로 이동
if (arrA[mid] == arrB[mid])
low = mid;
else
high = mid;
// low와 high가 인접해지면 반복 종료
if (low == high - 1)
break;
}
// 누락된 요소는 더 큰 배열의 high 인덱스에 위치
return arrA[high];
}
// 기본적인 오류 검사를 수행한 뒤
// findMissingUtil을 호출하는 함수
void findMissing(int arrA[], int arrB[], int P, int Q){
if (Q == P-1)
cout << "Missing Element is "
<< findMissingUtil(arrA, arrB, P) << endl;
else if (P == Q-1)
cout << "Missing Element is "
<< findMissingUtil(arrB, arrA, Q) << endl;
else
cout << "Invalid Input";
}
// 드라이버 코드
int main(){
int arrA[] = {2, 5, 6, 8, 10};
int arrB[] = {5, 6, 8, 10};
int P = sizeof(arrA) / sizeof(int);
int Q = sizeof(arrB) / sizeof(int);
findMissing(arrA, arrB, P, Q);
return 0;
}출력 결과
Missing Element is 2
복잡도 분석
- 시간 복잡도: O(log n) — 매 반복마다 탐색 범위가 절반으로 줄어듭니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.