[C] LeetCode 41. First Missing Positive

문제(원문)

문제(번역)

정렬되지 않은 정수 배열 nums가 주어진다. 이때 nums에 없는 가장 작은 양의 정수를 반환해라.

반드시 반드시 반드시 O(n)의 시간복잡도를 가지면서 O(1)의 공간복잡도를 갖는 알고리즘을 구현해라.

접근 방법

처음에 보자마자 떠오른 생각은 단순하게 배열을 만들어서 flag 형식으로 수가 나왔는지 확인하려 했다. 

그러나 수의 범위가 매우 크고 무엇보다 위에 O(1) // 추가적인 선형 배열 없이 구현하라고 나와있었다.

 

비상이다.

감이 잡히지 않아 AI에게 힌트를 달라고 했다.

AI 왈 입력 배열 자체를 값의 존재 여부를 표현하는 구조로 쓰라고 한다. 

 

즉 입력받은 배열을 순회하면서 계속해서 해당 원소를 해당 원소의 인덱스로 보내버리면 된다.

배열 순회가 끝나면 다시 배열을 순회하면서 i자리에 i+1값이 있는지 확인하고, 해당 값이 아니라면 그 수는 없는 것이기에 해당 수를 반환하면 된다.

소스 코드

int firstMissingPositive(int* nums, int numsSize) {
    int i, idx, tmp;
    for(i = 0; i<numsSize; i++) {
        while(nums[i] >= 1 && nums[i] <= numsSize && nums[i] != nums[nums[i]-1]) {
            idx = nums[i] - 1;
            tmp = nums[idx];
            nums[idx] = nums[i];
            nums[i] = tmp;
        }
    }
    for(i=0; i<numsSize; i++) {
        if(nums[i] != i + 1) {
            break;
        }
    }
    return i+1;

}

 

이렇게 접근하면 while 한번 돌 때 마다 적어도 하나의 값이 자기 자리로 가기 때문에 O(n)으로 볼 수 있다.

추가적인 선형 배열 선언도 없었으니 O(1)의 공간복잡도를 가진다.