[leetcode 매일 풀기] 41. first missing positive

오늘 리뷰할 문제는 first missing positive

 

https://leetcode.com/problems/first-missing-positive/description/

First Missing Positive - LeetCode

 

이 문제는 정렬되지 않은 숫자열에서, 빠져있는 제일 작은 양의 정수를 찾는 문제이다.

 

예를 들어 [1, 2, 0] 이 들어왔을 때, 3이 빠져있는 제일 작은 양의 정수이므로 구하면 된다.

 

그냥 막 짜라고 했다면, 일단 nlogn 정렬을 돌린 후, binary search로 1을 찾은 뒤, 구멍이 나는 정수를 찾는 식으로 구하면 됐을 텐데.

문제의 조건중에 시간 복잡도를 O(n)과 (n은 숫자열의 사이즈) 추가적인 공간복잡도를 O(1)인 알고리즘을 찾으라고 했다.

일단 두 제한 조건을 들었을 때는 순회를 한번에 하고, 기존에 있는 array를 override하면서 하는 접근을 해야겠다고 생각이 들었지만, 구체적인 알고리즘이 떠오르지 않아 다른 사람의 solution을 보고 이해한 뒤 직접 구현하는 방식으로 했다.

 

ammortized time complexity 개념으로 O(n)이 되는 solution인데 일단 코드는 아래와 같다.

from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            while 1 <= nums[i] <= len(nums) and nums[i] != nums[nums[i] - 1]:
                temp = nums[nums[i] - 1]
                nums[nums[i] - 1] = nums[i]
                nums[i] = temp
        res = 1
        for num in nums:
            if num != res:
                break
            res += 1
        return res


assert Solution().firstMissingPositive([1, 2, 0]) == 3
assert Solution().firstMissingPositive([3, 4, -1, 1]) == 2
assert Solution().firstMissingPositive([7, 8, 9, 11, 12]) == 1
assert Solution().firstMissingPositive([2, 1]) == 3

 

두번의 순회가 나오는데

1. 첫번째 순회에서는 sort를 진행하는데, 목표는 숫자 1,2,3을 숫자열의 0, 1, 2.. 번째 위치에 있을 때까지 옮겨주는 역할이다.

1-1 첫 구현때 while이 아닌 if를 사용하면, 안된다. 연쇄적으로 위치를 바꿔줘야 하는 케이스가 존재한다.

2. 빠진 양수가 어떤 것인지 찾는 역할

 

41 first missing positive 채점 결과

 

이렇게 풀면 딱 중위정도의 결과가 나온다.

 

더 빠른 방법은 아래처럼 set을 만들고 난 다음 체크하는 것인데. 추가적인 space complexity가 O(1)이라는 조건에 맞지 않기 때문에 적합하지 않은 solution으로 보았다.

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        MAX = max(nums)
        nums = set(nums)
        for i in range(1, MAX):
            if i > 0 and i not in nums:
                return i
        return max(1, MAX + 1)