[leetcode] First Missing Positive

문제

• 링크
• 정렬되지 않은 nums 배열이 주어진다. 이 배열에 포함되지 않으면서 가장 작은 자연수를 구해야한다. 시간 복잡도는 O(n)이고 추가적인 공간 복잡도는 O(1)이어야 한다.
• 제약 조건
  • 배열 길이: 1 <= nums.length <= 10^5
  • 값 범위: -2^31 <= nums[i] <= 2^31 - 1

풀이

풀기 전

• 아이디어가 안 떠올라서 discussion을 참고했다.
• 핵심 아이디어는 배열 길이를 n이라고 할 때, 정답의 범위가 [1, n+1]이라는 거다. 만약 nums = [1, 2, 3, ... n-1, n]이라면 정답은 n+1이다. 하지만 값이 하나라도 바뀌면 정답의 범위는 [1, n]이 된다. 특정 자연수 값이 비어버리기 때문이다.
• 그래서 nums를 순회하면서 [1, n]에 방문 체크를 한 뒤에, 방문되지 않은 값이 있으면 반환하면 된다. 또는 모두 방문됐으면 n+1을 반환하면 된다. 그런데 추가적인 공간 복잡도가 상수 시간이어야 하므로, set을 따로 만들 순 없다. 그렇다면 주어진 nums를 사용해서 방문 체크를 해줄 수 있겠다.

코드

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        
        // 음수이거나 n을 벗어나는 값은 따로 전처리를 해준다.
        // 방문했다는 의미와는 다른 값으로 처리한다.
        for (int i=0; i<n; i++) {
            if (nums[i] < 0 || nums[i] > n)
                nums[i] = 0;
        }

		// 값을 순회하며 방문 체크 해준다.
        for (int i=0; i<n; i++) {
            // 방문했다는 의미를 n+1로 해줬다. 값이 n+1이면 이미 방문한 곳이다.
            if (nums[i] == n+1)
                continue;

            int num = nums[i];
            int next_idx;
            while (num > 0 && num <= n) {
            	// num의 방문 처리를 하기 위해 nums[num - 1]에 방문 표시를 해준다.
                // 그리고 기존에 nums[num - 1]에 있던 값으로 다시 방문 표시를 해주기 위해 num에 넣어준다.
                // num이 [1, n]에 속해있는 동안 이를 반복한다.
                next_idx = num - 1;
                num = nums[next_idx];
                nums[next_idx] = n + 1;
            }
        }

		// nums를 순회하며 방문 체크 되지 않은 곳이 있으면 반환한다.
        for (int i=0; i<n; i++) {
            if (nums[i] != n + 1)
                return i + 1;
        }
        // 모두 방문 체크 되었다면 n+1을 반환한다.
        return n + 1;
    }
}

푼 후

• 어려웠다.
• 방문 체크를 해줘야 할 거 같은데 정답의 범위가 [1, n+1]인 것을 알아채지 못해서 헤맸다. 정답 범위를 제한적이라는 걸 떠올린다면 주어진 nums로 방문 체크 한다는 생각까지 자연스럽게 이어질 수 있을 거 같다.