Python으로 찾는 첫 번째 누락된 양의 정수

정렬되지 않은 정수 배열이 하나 주어졌다고 가정해 보겠습니다. 이때 배열에 존재하지 않는 가장 작은 양의 정수를 찾아야 합니다. 예를 들어 배열이 [4, -3, 1, -1]이라면 1은 존재하지만 2는 없으므로 결과는 2가 됩니다.

문제 해결 접근 방법

이 문제는 인덱스 기반 자리 바꾸기 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 양수 값을 자신이 있어야 할 인덱스 위치로 옮긴 뒤, 배열을 순회하면서 기대하는 값과 실제 값이 처음 어긋나는 지점을 찾는 것입니다. 음수와 범위를 벗어나는 값은 무시됩니다.

구체적인 해결 단계는 다음과 같습니다.

• 인덱스 i를 0으로 설정하고, 모든 숫자 앞에 0을 하나 추가하여 nums 배열을 갱신합니다. 이렇게 하면 값과 인덱스가 1:1로 대응되어 계산이 단순해집니다.
• 0부터 nums의 길이까지 반복합니다.
• nums[i]가 0 이상이고 nums의 길이 미만이며, nums[nums[i]]가 nums[i]와 같지 않은 동안 두 값을 서로 교환하여 각 값을 올바른 위치로 보냅니다.
• num을 1로 초기화합니다.
• 1부터 nums의 길이까지 순회하면서 num이 nums[i]와 같으면 num을 1씩 증가시킵니다.
• 순회가 끝난 후 num을 반환합니다. 이 값이 곧 첫 번째로 누락된 양의 정수입니다.

예제 코드

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

class Solution(object):
    def firstMissingPositive(self, nums):
        nums = [0] + nums
        # 각 값을 올바른 인덱스 위치로 이동
        for i in range(len(nums)):
            while 0 <= nums[i] < len(nums) and nums[nums[i]] != nums[i]:
                nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        # 첫 번째로 누락된 양의 정수 탐색
        num = 1
        for i in range(1, len(nums)):
            if num == nums[i]:
                num += 1
        return num

ob = Solution()
print(ob.firstMissingPositive([4, -3, 1, -1]))

입력

[4,-3,1,-1]

출력

2

복잡도 분석

• 시간 복잡도: O(n) — 각 원소는 자리 교환 과정에서 최대 한 번씩만 올바른 위치로 이동하므로 전체 연산 횟수는 선형적으로 증가합니다.
• 공간 복잡도: O(n) — 위 예제에서는 0을 추가한 새 리스트를 생성하지만, 입력 배열을 직접 수정하면 추가 공간 없이 O(1)로 처리할 수 있습니다.

이처럼 정렬이나 해시 집합을 사용하는 대신 배열 자체를 활용하면, 추가 자료 구조 없이도 누락된 양의 정수 문제를 깔끔하고 효율적으로 해결할 수 있습니다.