Python으로 정렬된 숫자 목록에서 k번째 누락된 숫자 찾는 방법

문제 개요

정렬된 고유한 숫자로 이루어진 목록 nums와 정수 k가 주어졌을 때, 목록의 첫 번째 요소를 기준으로 k번째로 누락된 숫자를 찾아야 합니다.

예를 들어, nums = [5,6,8,10,11], k = 1이 입력으로 주어지면 출력은 9입니다. 이 목록에서 누락된 숫자는 7과 9이며, 9는 두 번째(인덱스 1)에 해당하는 누락된 숫자이기 때문입니다.

해결 접근 방식

핵심 아이디어는 인접한 두 숫자 사이에 몇 개의 숫자가 누락되었는지 계산하고, k를 순차적으로 차감하면서 답이 위치한 구간을 찾는 것입니다.

1. 인덱스 1부터 목록의 끝까지 반복합니다.
2. diff = nums[i] - nums[i-1] - 1로 현재 구간에서 누락된 숫자의 개수를 구합니다.
3. k >= diff라면 이 구간의 누락된 숫자를 모두 건너뛸 수 있으므로 k -= diff로 갱신합니다.
4. 그렇지 않다면 답은 현재 구간 안에 있으므로 nums[i-1] + k + 1을 반환합니다.
5. 모든 구간을 확인한 후에도 답을 찾지 못했다면 목록의 마지막 숫자 뒤에 답이 있는 것이므로 nums[-1] + k + 1을 반환합니다.

구현 예제

class Solution:
    def solve(self, nums, k):
        for i in range(1, len(nums)):
            diff = nums[i] - nums[i - 1] - 1
            if k >= diff:
                k -= diff
            else:
                return nums[i - 1] + k + 1
    return nums[-1] + k + 1

ob = Solution()
nums = [5,6,8,10,11]
k = 1
print(ob.solve(nums, k))

입력

[5,6,8,10,11], 1

출력

9

동작 과정 살펴보기

위 코드가 어떻게 9를 반환하는지 단계별로 확인해 보겠습니다.

• i = 1: diff = 6 − 5 − 1 = 0 (누락된 숫자 없음). k ≥ diff이므로 k는 그대로 1입니다.
• i = 2: diff = 8 − 6 − 1 = 1 (숫자 7이 누락됨). k ≥ diff이므로 k는 0이 됩니다.
• i = 3: diff = 10 − 8 − 1 = 1 (숫자 9가 누락됨). k < diff이므로 nums[2] + 0 + 1 = 9를 반환합니다.

복잡도 분석

• 시간 복잡도: O(n) — 목록을 한 번만 순회하면 됩니다.
• 공간 복잡도: O(1) — 추가적인 메모리를 사용하지 않습니다.