파이썬으로 배열에 없는 가장 작은 양의 정수를 찾는 방법

리스트 형태의 숫자 목록 nums가 주어졌을 때, 이 중에서 가장 먼저 빠져 있는 양의 정수를 찾아야 합니다. 즉, 배열에 존재하지 않는 가장 작은 양의 정수를 구하는 문제입니다. 배열에는 중복된 숫자나 음수가 포함될 수도 있습니다.

예를 들어, 입력이 nums = [0, 3, 1]이라면 출력 결과는 2가 됩니다.

문제 해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

• nums에서 양수만 골라 새로운 집합(set)을 만듭니다.

• 집합이 비어 있다면, 즉 양수가 하나도 없다면 1을 반환합니다.

• 1부터 집합 크기 + 2까지 반복하면서 해당 값이 집합에 없으면 그 값을 반환합니다.

구현 예제

아래 파이썬 코드를 통해 더 자세히 살펴보겠습니다.

class Solution:
    def solve(self, nums):
        nums = set(num for num in nums if num > 0)

        if not nums:
            return 1
        for i in range(1, len(nums) + 2):
            if i not in nums:
                return i

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

입력

[0,3,1]

출력

2

코드 설명

이 알고리즘의 핵심 아이디어는 다음과 같습니다.

1. 양수 필터링: 문제에서 요구하는 것은 '양의 정수'이므로, 0 이하의 값은 모두 제외하고 양수만 집합에 담습니다. 집합을 사용하면 중복도 자동으로 제거되며, 멤버십 검사(i not in nums)가 평균 O(1) 시간에 이루어져 효율적입니다.
2. 빈 집합 처리: 배열에 양수가 전혀 없다면 정답은 항상 1입니다.
3. 순차 탐색: 1부터 차례대로 확인하여 처음으로 빠진 값을 반환합니다. 집합의 크기를 n이라 할 때, 답은 반드시 1부터 n+1 사이에 존재하므로 range(1, len(nums) + 2) 범위로 충분합니다.

전체 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로, 이 문제를 효율적으로 해결할 수 있는 방법입니다.