파이썬으로 누락된 숫자 찾기 — 이진 탐색을 활용한 효율적인 풀이법

0부터 n까지의 숫자로 구성된 리스트가 있다고 가정해 보겠습니다. 그런데 이 중 한 개의 숫자가 누락되어 있습니다. 우리의 목표는 비효율적인 전수 조사가 아닌, 효율적인 알고리즘으로 이 누락된 숫자를 찾아내는 것입니다.

예를 들어, 리스트가 다음과 같다면:

A = [0, 1, 2, 3, 4, 5, 7, 8, 9]

여기서 빠진 숫자는 6입니다. 이 문제는 이진 탐색(Binary Search) 기법을 활용하면 매우 효율적으로 해결할 수 있습니다.

알고리즘 접근 방식

이진 탐색을 적용하는 핵심 아이디어는 간단합니다. 오름차순으로 정렬된 배열에서 인덱스와 값이 일치하지 않는 첫 번째 지점 바로 앞이 곧 누락된 숫자의 위치이기 때문입니다. 단계별 과정은 다음과 같습니다.

1. 리스트를 오름차순으로 정렬합니다.
2. high를 리스트의 길이로, low를 0으로 초기화합니다.
3. low < high인 동안 아래 과정을 반복합니다:
   • mid = low + (high - low) // 2로 중간 지점을 계산합니다.
   • 만약 nums[mid] > mid라면, 누락된 숫자가 왼쪽 절반에 있으므로 high = mid로 설정합니다.
   • 그렇지 않다면, 누락된 숫자가 오른쪽 절반에 있으므로 low = mid + 1로 설정합니다.
4. 반복이 종료되면 low 값을 반환합니다. 이것이 곧 누락된 숫자입니다.

파이썬 구현 예제

아래 코드를 통해 실제 동작을 더 잘 이해해 보겠습니다.

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        high = len(nums)
        low = 0
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] > mid:
                high = mid
            else:
                low = mid + 1
        return low

ob1 = Solution()
print(ob1.missingNumber([5,3,1,7,8,0,9,2,4]))

입력

nums = [5,3,1,7,8,0,9,2,4]

출력

6

시간 복잡도 분석

이 알고리즘은 정렬에 O(n log n)이 소요되며, 이후 이진 탐색 자체는 O(log n) 만에 완료됩니다. 따라서 전체 시간 복잡도는 O(n log n)입니다. 만약 입력이 이미 정렬되어 있다면 탐색 부분만 고려하면 되므로 O(log n)만으로 해결됩니다.

마무리

누락된 숫자를 찾는 문제는 코딩 테스트와 면접에서 자주 등장하는 대표적인 유형입니다. 이진 탐색을 활용하면 선형 탐색(O(n))보다 훨씬 적은 비교 횟수로 답을 찾을 수 있어, 대규모 데이터에서도 뛰어난 성능을 발휘합니다. 위 코드를 직접 실행해 보면서 각 단계에서 low, high, mid 값이 어떻게 변하는지 추적해 보면 이해가 더욱 깊어질 것입니다.