[LeetCode/릿코드] - 41. First Missing Positive - (Hard/하드)

엊그제, 미국 도착!! 폰 개통하고, 계좌 오픈하고, 화이자 맞고!
이제 부지런히 문제 풀어야지... 
오늘 부터 던킨 도넛에서 아침 먹으면서 문제 풀기 시작!

Hard 문제인데, 문제 해석은, 빼먹은 양의 정수중 가장 작은 숫자를 반환하면 되는 문제!

Given an unsorted integer array nums, find the smallest missing positive integer.
You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:
Input: nums = [1,2,0] Output: 3

Example 2:
Input: nums = [3,4,-1,1] Output: 2

Example 3:
Input: nums = [7,8,9,11,12] Output: 1

Constraints:

• 1 <= nums.length <= 5 * 10^5
• -2^31 <= nums[i] <= 2^31 - 1

 

문제 해설 :
처음에 Direct Addressing Table로 문제를 풀었다. 
Runtime Error 발생해서 보니, 숫자 제한 자체가 최대 2^31 - 1 이더라.
분명히 속도는 잘 맞아 떨어질텐데, 메모리 때문이라면 배열 저장해서 풀리지 않겠더라.
숫자 개수 자체는 50000 개라서 그냥 정렬 때렸다. 

아이디어 : 
1. 양의 정수 중, 인풋에 없는 최소 숫자를 찾아야한다.
2. 즉, 1부터 시작하는 숫자들부터 인풋에 없는 숫자를 찾기만 하면된다. 
3. 연속적인 숫자를 제외한 숫자를 찾는게 아니라, 1부터 순서대로 확인하면서 저장되지 않는 숫자를 리턴하면된다.
4. 여기서 조심해야할 것은, 음수만 있을때랑, 1부터 연속된 숫자가 존재할때, 가장 큰 숫자에 + 1 을 리턴하면 된다.
5. 하지만, 제약사항을 보면 값들은 최대가 50000 까지고, 숫자의 개수는 2^31 - 1 이다. 그래서, Hash 나 Direct Addressing Table 을 사용하면, 메모리를 사용하면 Runtime Error 가 발생한다.
6. 결국, O(n) 으로 구해야하기 때문에 다른 방법을 사용해야하는데, 정렬은 O(NlogN)의 시간이 걸리기 때문에 가지치기를 하면 해결되더라.
7. 최대값이 50000 밖에 되지 않기 때문에 정렬로 데이터를 정리하고, 리스트를 for 으로 돌려서 최소값이 배열에 없는 거면 리턴해준다.
* 문제의 예제중에 연속된 숫자가 존재할 수 있기 때문에 그부분도 가지치기 해주자.

결국, 정렬 자체가 O(NlogN) 이나 중간에 가지치기랑 숫자 최대값이 크지 않기 때문에 해결 됬다.
최적화하는 방법은 그냥 비트 연산으로 배열 만들어서 하면 가능할 것 같은데... 음 ... Next.

정답 코드 : 

# Source Code
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        maxValue = max(nums) + 1
        minValue = 21e8
        nSize = len(nums)
        nums.sort()
        start = 1
        flag = 0

    for ii in range(nSize):
        i = nums[ii]
        if i > 0:
            if ii > 0 and nums[ii] == nums[ii - 1]:
                continue
            if i == start:
                start += 1
            else:
                return start

    if maxValue <= 0:
        return 1
    else:
        return maxValue

# The End by Saurus2