문제 개요
두 개의 배열이 있고, 이 둘은 단 하나의 요소를 제외하면 완전히 동일한(복제 관계인) 배열이라고 가정해 보겠습니다. 즉, 한쪽 배열에만 존재하는 요소가 하나 있다는 의미입니다. 우리의 목표는 바로 이 누락된 요소를 찾아내는 것입니다.
예를 들어 입력이 A = [2, 5, 6, 8, 10], B = [5, 6, 8, 10]이라면, 두 번째 배열에는 2가 존재하지 않으므로 결과값은 2가 됩니다.
해결 접근 방식
두 배열이 정렬되어 있다는 전제 조건이 있다면, 선형 탐색 대신 이진 탐색(Binary Search)을 활용하여 O(log N)의 시간 복잡도로 매우 효율적으로 답을 구할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 누락된 요소가 등장하기 이전 인덱스에서는 두 배열의 값이 항상 일치합니다.
- 누락된 요소가 등장한 이후 인덱스부터는 두 배열의 값이 어긋나기 시작합니다.
- 따라서 이진 탐색으로 두 배열이 처음으로 달라지는 지점을 찾으면, 그 지점의 A 배열 값이 곧 누락된 요소입니다.
알고리즘 단계
solve()함수를 정의합니다. 이 함수는 A, B, N 세 개의 매개변수를 받습니다.- N이 1이면
A[0]을 반환합니다. A[0]과B[0]이 다르다면 첫 번째 요소 자체가 누락된 것이므로A[0]을 반환합니다.low := 0,high := N - 1로 초기화합니다.low < high인 동안 다음을 반복합니다.mid := (low + high) / 2로 중간 인덱스를 계산합니다.A[mid] == B[mid]이면low := mid로 갱신합니다.- 그렇지 않으면
high := mid로 갱신합니다. low == high - 1이 되면 루프를 종료합니다.
A[high]를 반환합니다. 이것이 누락된 요소입니다.- 메인 로직에서는 다음과 같이 처리합니다.
- M := A의 크기, N := B의 크기로 설정합니다.
- N이 M - 1과 같으면(긴 배열이 A)
solve(A, B, M)을 호출합니다. - M이 N - 1과 같으면(긴 배열이 B)
solve(B, A, N)을 호출합니다. - 그 외의 경우 크기 차이가 1이 아니므로
"Not found"를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 구현 과정을 확인할 수 있습니다.
def solve(A, B, N):
if N == 1:
return A[0]
if A[0] != B[0]:
return A[0]
low = 0
high = N - 1
while (low < high):
mid = (low + high) / 2
if A[mid] == B[mid]:
low = mid
else:
high = mid
if low == high - 1:
break
return A[high]
def get_missing_element(A, B):
M = len(A)
N = len(B)
if N == M - 1:
return solve(A, B, M)
elif M == N - 1:
return solve(B, A, N)
else:
return "Not found"
A = [2, 5, 6, 8, 10]
B = [5, 6, 8, 10]
print(get_missing_element(A, B))입력
[2, 5, 6, 8, 10], [5, 6, 8, 10]
출력
2
시간 및 공간 복잡도
- 시간 복잡도: O(log N) — 매 반복마다 탐색 범위가 절반으로 줄어드는 이진 탐색을 사용하기 때문입니다.
- 공간 복잡도: O(1) — 추가적인 배열이나 자료구조 없이 몇 개의 변수만 사용합니다.
만약 배열이 정렬되어 있지 않다면 해시 집합(set)을 이용해 두 배열의 차집합을 구하는 O(N) 방법을 고려할 수 있습니다. 하지만 정렬된 배열이라는 조건이 주어진다면 위의 이진 탐색 기법이 가장 효율적인 선택입니다.