[2024] day 87. Leetcode 41. First Missing Positive

gunny·2024년 3월 26일

41. First Missing Positive 41. First Missing Positive python leetcode 41. First Missing Positive leetcode 41. First Missing Positive python

코딩테스트

목록 보기

400/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 26일 (화)
Leetcode daily problem

41. First Missing Positive

https://leetcode.com/problems/first-missing-positive/?envType=daily-question&envId=2024-03-26

Problem

정렬되지 않은 정수 배열 nums가 주어질 때, nums에 존재하지 않는 가장 작은 양의 정수를 반환한다.
O(n) 시간에 실행되고 O(1) 보조 공간을 사용하는 알고리즘을 구현해야 한다.

Solution

cycle sort

cycle sort : 정렬 알고리즘 중 하나이다.
합병 정렬이나 퀵 정렬과 같은 일반적인 정렬 알고리즘과 다르다.
추가적인 메모리 공간을 사용하지 않는 "인-플레이스(in-place)" 정렬이다.

기본 아이디어는 각 순회(iteration)에서 현재 인덱스에 해당하는 값에 맞는 적절한 인덱스로 옮긴다. 맞는 인덱스에 값을 옮길때 해당 인덱스의 값은 적절한 인덱스의 값과 교환된다. 이 과정이 모든 요소가 올바른 위치에 있을 때까지 반복한다.

이러한 특징으로 cycle sort는 값들이 거의 정렬되어 있는 경우에도 유용한데, 다른 정렬 알고리즘은 O(nlogn)의 시간복잡도를 가지지만, cycle sort는 최악의 경우 O(n^2)의 시간복잡도를 갖는다.

주요 특징은 같은 값의 상대적인 위치가 변하지 않아 안정적인 정렬이 가능하고, 추가적인 메모리를 사용하지 않는다. 이미 거의 정렬되어 있는 경우 교환 연산의 수를 줄이기 위해 효과적이다.

cycle 정렬을 완벽히 구현하려면 공간 이동이 가능해야 한다고 한다. 자료들이 cycle 관계에 있는 그룹을 찾아내 정렬 기준에 맞게 자료들을 회전시켜서 정렬하는 방법이다.

Code

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        
        while i < n:
            idx = nums[i] -1
            if 0 < nums[i] <=n and nums[i] != nums[idx]:
                nums[i], nums[idx] = nums[idx], nums[i]
            else:
                i +=1
        
        for i in range(n):
            if nums[i] != i+1:
                return i+1
            
        return n+1