Python으로 배열에서 첫 번째 누락된 양의 정수 찾기

문제 개요

크기가 n인, 서로 다른 정수로 이루어진 정렬된 리스트가 주어졌다고 가정해 봅시다. 이때 [1부터 n+1] 범위 안에서 배열에 존재하지 않는 첫 번째 양의 정수를 찾아야 합니다.

예를 들어 입력이 nums = [0, 5, 1]이라면 출력은 2가 됩니다. 1부터 시작해 차례대로 확인할 때 가장 먼저 빠져 있는 숫자가 2이기 때문입니다.

해결 접근 방법

이 문제는 간단한 선형 탐색으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '다음으로 기대되는 값'을 추적하는 것입니다. 단계별로 살펴보면 다음과 같습니다.

• 찾고자 하는 값을 나타내는 변수 target을 1로 초기화합니다.
• 배열의 각 요소 i를 순서대로 확인하면서, i가 target과 같다면 해당 값이 존재하는 것이므로 target을 1 증가시킵니다.
• 배열의 모든 요소를 확인한 뒤 최종 target 값을 반환합니다. 이 값이 바로 배열에 없는 첫 번째 양의 정수입니다.

배열이 정렬되어 있고 중복이 없다는 전제 조건 덕분에 이 한 번의 순회만으로 정답을 보장할 수 있습니다.

구현 예제

다음 코드를 통해 더 잘 이해해 보겠습니다.

class Solution:
    def solve(self, arr):
        target = 1
        for i in arr:
            if i == target:
                target += 1
        return target

ob = Solution()
nums = [0, 5, 1]
print(ob.solve(nums))

입력

[0, 5, 1]

출력

2

동작 원리 상세 설명

입력 [0, 5, 1]에 대해 알고리즘이 어떻게 진행되는지 단계별로 살펴보겠습니다.

• 초기 상태: target = 1
• i = 0 → 0은 target(1)과 다르므로 변화 없음
• i = 5 → 5는 target(1)과 다르므로 변화 없음
• i = 1 → 1은 target(1)과 같으므로 target = 2로 증가
• 순회 종료 후 2 반환

복잡도 분석

시간 복잡도: O(n) — 배열의 모든 요소를 한 번씩만 확인하면 됩니다.
공간 복잡도: O(1) — 추가적인 자료 구조 없이 단일 변수만 사용하므로 메모리 사용량이 일정합니다.

마무리

이처럼 '기대값 추적' 기법을 활용하면 집합(set)이나 정렬 재작업 없이도 누락된 첫 번째 양의 정수를 선형 시간 안에 찾을 수 있습니다. 배열이 정렬되어 있다는 조건이 주어진 문제라면 이 방식이 가장 깔끔하고 효율적인 선택입니다.