문제 개요
등차수열의 항 n-1개가 담긴 배열 nums가 있다고 가정해 보겠습니다. 이 배열에서 첫 번째 항이나 마지막 항을 제외한 하나의 요소가 미리 제거되었고, 우리의 목표는 바로 그 제거된 숫자를 찾아내는 것입니다.
예를 들어 입력이 nums = [5, 7, 11, 13]이라면 출력은 9가 됩니다. 이 수열의 항들은 2i+5 공식을 따르는데, i = 2일 때 2*2 + 5 = 9가 되어야 하지만 해당 값이 빠져 있기 때문입니다.
해결 접근 방식
이 문제는 이진 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 각 인덱스 위치의 실제 값이 등차수열 공식에 맞는지 확인하면서, 어긋나는 지점을 점점 좁혀 나가는 방식입니다. 구체적인 단계는 다음과 같습니다.
- 배열의 크기가 2라면, 모든 요소의 합을 2로 나눈 몫을 반환합니다.
- nums[0]과 nums[1]이 같다면 nums[0]을 반환합니다.
- lower := nums[0], upper := 배열의 마지막 요소로 설정합니다.
- interval := (upper - lower) // len(nums) 로 공차를 계산합니다.
- pointer := len(nums) // 2 로 중간 지점을 지정합니다.
- left := 0, right := len(nums) - 1 로 탐색 범위를 초기화합니다.
- left와 right가 같아질 때까지 아래 과정을 반복합니다.
- nums[pointer]가 nums[0] + interval * pointer와 다르다면:
- nums[pointer - 1]이 nums[0] + interval * (pointer - 1)과 같다면, nums[0] + interval * pointer가 곧 제거된 값이므로 이를 반환합니다.
- 그렇지 않다면 right := pointer로 탐색 범위를 왼쪽으로 좁히고, pointer := (left + right) // 2 로 갱신합니다.
- 값이 일치한다면:
- right - left == 1이라면 pointer := right로 설정합니다.
- 그렇지 않다면 left := pointer로 탐색 범위를 오른쪽으로 좁히고, pointer := (left + right) // 2 로 갱신합니다.
- nums[pointer]가 nums[0] + interval * pointer와 다르다면:
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
def solve(nums):
if len(nums) == 2:
return sum(nums) // 2
if nums[0] == nums[1]:
return nums[0]
lower = nums[0]
upper = nums[-1]
interval = (upper - lower) // len(nums)
pointer = len(nums) // 2
left = 0
right = len(nums) - 1
while left != right:
if nums[pointer] != nums[0] + interval * pointer:
if nums[pointer - 1] == nums[0] + interval * (pointer - 1):
return nums[0] + interval * pointer
else:
right = pointer
pointer = (left + right) // 2
else:
if right - left == 1:
pointer = right
else:
left = pointer
pointer = (left + right) // 2
nums = [5, 7, 11, 13]
print(solve(nums))
입력
[5, 7, 11, 13]
출력
9
마무리
이 알고리즘은 반복할 때마다 탐색 범위를 절반씩 줄여 나가므로 O(log n)의 시간 복잡도로 동작합니다. 모든 요소의 합을 이용해 누락된 값을 구하는 O(n) 방식보다 효율적이며, 특히 배열의 크기가 매우 클 때 그 장점이 두드러집니다.