[Misc][Hard] 41. First Missing Positive

https://leetcode.com/problems/first-missing-positive/description

 

 

Q. 정렬되지 않은 정수 배열 nums가 주어질 때, 배열안에 없는 가장 작은 양수를 찾아라. 

 O(N)의 TC에 O(1)의 space를 사용하라.

 

 

Solution

 추가 메모리를 쓰면 간단하다. 

 하지만, 여기서는 그렇게 하면 안되므로, 다른 방법을 고려한다. 

 

 존재하는 수를 특정 방식으로 걸러내에 존재하지 않는 수를 찾아낸다.

 

 여기서는 음수화를 취한다. 

 

 우선 루프를 돌며, 해당 값을 nums 배열과 매칭 시킨다면, 범위 바깥이 될 수를 골라내 범위 안 최소 값으로 초기화 한다.

 모든 수가 존재한다면, 범위 밖 수는 없게 된다. 

 

 이 값을 index로 변환하고, 이 index위치에 해당하는 값들을 음수로 바꾼다. 

 그러면 존재하지 않는 값들을 제외하면 모두 음수가 된다. 

 이때 주의 할 점은 음수로 만든 index의 값이 다시 사용될 수 있으므로, 항상 절대값을 먼저 취하고 음수를 set한다.

 

 마지막으로 loop를 돌면서 음수가 아닌 수를 찾으면 그 수가 존재하지 않는 첫번째 양의 정수가 된다. 

 

로직대로 코드를 만든다. 

 

 

public int FirstMissingPositive(int[] nums) 
{
    int len = nums.Length;
    bool foundOne = false;

    // 1을 찾거나, 범위 밖 값을 범위 안 1로 set 한다.
    for(int k = 0; k < nums.Length; ++k)
    {
        if(nums[k] == 1)
            foundOne = true;

        if(nums[k]<1 || nums[k]>nums.Length)
            nums[k] = 1;
    }

    if(!foundOne)   return 1;

    // Key : 안에 존재하는 모든 값에 대해, 해당 index가 음수를 갖게 한다.
    for(int k = 0; k < nums.Length; ++k)
    {
        int idx = Math.Abs(nums[k]);
        nums[idx-1] = -Math.Abs(nums[idx-1]);
    }

    // 음수가 아니면 nums안에 값이 존재하지 않는 것이다. 
    for(int k = 0; k < nums.Length; ++k)
    {
        if(nums[k]>0)   return k+1;
    }

    // 모두 음수라면, 수가 다 존재하는 것이므로, 길이바로 다음값이 없는 값이 된다.
    return nums.Length+1;
}

 

 적당한 결과를 얻었다.

 

 

Note) 이런 류의 문제도 제법 나온다. 

 좋은 문제. 

 알아 두자.