41. First Missing Positive

정렬되지 않은 리스트에서 존재하지 않는 가장 작은 양수를 찾는 문제이다.

 

그냥 정렬시키고 작은 수부터 찾으면 되지 않냐고 할 수 있겠지만, 위에서처럼 O(n) 시간을 가지는 알고리즘으로 풀기를 원하고 있다.

 

처음에 생각한 방법

1. stamp 리스트를 리스트 중 가장 큰 수의 길이를 갖도록 만든다.
2. stamp[nums[i]] = 1 을 하여 수가 존재함을 표시해준다.
3. for문을 통해 index = 1부터 차례대로 1이 표시되어 있지 않은 공간을 찾아 i를 리턴한다.

하지만 -2^31 <= nums[i] <= 2^31 - 1 의 크기를 가지고 있어서 단 하나의 수만 커도 배열 공간의 낭비가 크다.

 

따라서 나는 Dictionary를 이용해서 문제를 풀기로 했다.

1. dic[nums[i]] = 1 을 표시한다.
2. for문에서 i는 1부터 nums의 max값+ 2까지 dic.get(i) == None 이면 nums[i]를 리턴한다.

range(1,max + 2)인 이유는 만약 max = 10 일 경우 1부터 10까지 모두 존재할 경우 11이 최소가 되므로 index를 max+1까지 탐색하여야 한다.

 

또한, dic[i] 를 사용하면 대응되는 val이 없을 경우 에러가 나지만, dic.get(i)를 사용하는 경우 None을 리턴한다.

 

Hard 문제였지만 쉬웠다.

 

 

소스코드

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        dic = {}
        ma = 0
        for i in range(len(nums)):
            dic[nums[i]] = 1
            if ma < nums[i]:
                ma = nums[i]
        for i in range(1,ma+2):
            if dic.get(i) == None:
                return i