[LeetCode 풀이/python] 41. First Missing Positive (hard)

문제 설명: 정렬되지 않은 정수 배열 nums 가 주어졌을 때, 해당 배열에서 누락된 양의 정수 중 가장 작은 수를 찾으시오.

 

(Given an unsorted integer array nums, find the smallest missing positive integer.)

 

예시 1)

입력: nums = [1,2,0]  -->  출력: 3

 

예시 2)

입력: nums = [3,4,-1,1]  -->  출력: 2

 

예시 3)

입력: nums = [7,8,9,11,12]  -->  출력: 1

 

제한 조건:

• 0 <= nums.length <= 300
• -2^31 <= nums[i] <= 2^31 - 1

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 일단 배열을 오름차순 정렬한 후, 이진 탐색을 통해 해당 배열에 1 의 포함 여부 & 인덱스를 확인함  -->  없을 경우 1 을 리턴
  • 1 이 포함된 경우, 해당 인덱스에서부터 배열 끝까지 차례로 탐색하며 missing 값이 발생하는 지점 확인

 

• 코드 구현

def firstMissingPositive(nums: List[int]) -> int:
    nums = list(set(nums))
    nums.sort()
    no_one, one_idx = missing_one(nums)
    if no_one:
        return 1
    else:
        for i, j in enumerate(range(one_idx, len(nums))):
            if (i+1) != nums[j]: return (i+1)
        return nums[-1]+1
    
def missing_one(nums):
    l, r = 0, len(nums)-1
    
    while l <= r:
        mid = (l+r)//2
        if nums[mid] == 1: 
            return False, mid
            
        elif nums[mid] < 1:
            l = mid + 1
        else: 
            r = mid - 1
    return True, 0 

 

• 결과
  • 이진 탐색을 위해 배열을 정렬하는 데에 O(n log n) + 1 부터 탐색하는 데에 O(n)  -->  O(n log n) 소요
  • 다 풀고 보니 추가 조건(Follow-up) 이 있었다:
    • Could you implement an algorithm that runs in O(n) time and uses constant extra space?
    • 처음에 배열을 정렬하지 않고 탐색하는 건가... 나중에 O(n) 으로 다시 풀어봐야지 ㅎ_ㅎ