Python으로 배열에서 k번째 누락된 양수 찾는 방법

정렬되어 있고 엄격하게 증가하는 양의 정수로 구성된 배열 nums와 정수 k가 주어졌다고 가정해 봅시다. 이때 우리가 해야 할 일은 배열에 존재하지 않는 양의 정수 중에서 k번째로 작은 수를 찾는 것입니다.

예를 들어, 입력이 nums = [1,2,4,8,12], k = 6이라면 출력은 10이 됩니다. 그 이유는 누락된 숫자들이 [3,5,6,7,9,10,11]이고, 그중 여섯 번째 숫자가 바로 10이기 때문입니다.

해결 접근 방법

이 문제는 아래 단계를 따라 해결할 수 있습니다.

• 배열 요소들의 조회 속도를 높이기 위해 nums를 집합(set)으로 변환합니다.
• 누락된 숫자의 개수를 세기 위한 변수 count를 0으로 초기화합니다.
• 현재 검사 중인 숫자를 나타내는 변수 num을 1로 초기화합니다.
• count가 k보다 작은 동안 다음 과정을 반복합니다.
  • num이 집합에 없으면 count를 1 증가시킵니다.
  • count가 k와 같아지면 현재 num을 반환합니다.
  • num을 1 증가시킵니다.

즉, 1부터 시작해 차례대로 숫자를 확인하면서 배열에 없는 숫자를 만날 때마다 카운트를 늘려가고, k번째 누락된 숫자에 도달하면 그 값을 반환하는 단순하고 직관적인 방식입니다.

Python 코드 예제

아래 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(nums, k):
    nums = set(nums)
    count = 0
    num = 1
    while count < k:
        if num not in nums:
            count += 1
        if count == k:
            return num
        num += 1
    return num

nums = [1,2,4,8,12]
k = 6
print(solve(nums, k))

입력

[1,2,4,8,12], 6

출력

10

복잡도 분석

이 알고리즘은 최악의 경우 1부터 답까지 모든 숫자를 한 번씩 확인하므로 시간 복잡도는 O(n + k)입니다. 또한 배열을 집합으로 변환하는 데 추가 메모리가 필요하므로 공간 복잡도는 O(n)입니다.

참고로, 각 위치에서 계산할 수 있는 '실제 값과 인덱스의 차이'를 활용한 이진 탐색(binary search) 기법을 적용하면 시간 복잡도를 O(log n)까지 줄일 수 있습니다. 다만 위의 선형 탐색 방식이 코드가 간결하고 이해하기 쉬워 학습 목적에는 매우 적합합니다.