LeetCode: 41번 (First Missing Positive) [JAVA]

문제 링크

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

First Missing Positive - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 nums 배열을 돌며 1보다 작거나 배열의 길이를 넘는 수는 -1로 처리 (남는 수는 배열 길이 범위 내의 숫자)
2. 배열 속 숫자 처리를 위한 check 함수 선언
   1) 파라미터로는 주어진 nums 배열과 nums 배열 속 숫자(num)
   2) 만약 주어진 숫자가 1번에서 처리한 과정 이후의 배열 범위 내의 숫자라면
   3) nums[num] 숫자를 가져와 임시 저장
   4) 해당 위치는 0 처리 후 다시 한 번 check 함수에 nums 배열과 nums[num] 값을 넣어 호출
   
3. 이후 전체 배열을 돌며 check 함수 선언 후, 다시 한 번 배열을 돌며 특정 위치 값이 0이 아닌 경우 해당 위치 값+1을 반환 (없으면 배열 길이+1을 반환)
   

 문제 해결에 대한 아이디어를 얻으면 쉽게 해결할 수 있지만, 해당 아이디어를 떠올리는 게 너무 어려워 아이디어를 찾아보았던 문제이다. 결국 이 문제에서는 정렬이 되지 않은 nums 배열을 찾아보며, 결국 nums 배열 속에 등장하지 않은 가장 작은 양의 정수를 반환하는 문제이다. 또한 요구 사항으로 시간복잡도 O(N)의 로직과 상수 메모리 크기를 요구하기 때문에, 정렬 또한 진행하지 않고 문제를 해결해야 한다.
 결국 O(N)의 복잡도라면 대개 배열을 단순 돌기만하면서 문제의 해답을 완성해야 나가야 하는 로직을 필요로 하고, 그러면서 nums 배열에 등장하는 양의 정수들에 어떤게 있는지 모두 체크하고 이를 저장해야 하기 때문에 마땅한 답이 생각나지 않아 답에 대한 아이디어를 찾아보았다.
 문제 해결의 핵심은 바로 문제에 있는데, 주어진 문제에 대한 제한 사항들을 보면 nums 배열의 길이는 1~100000이라는 부분이다. 결국 우리가 찾아야 하는 숫자는 nums 배열 속 등장하지 않은 최소 양의 정수이고, nums 배열에 아무리 어떤 숫자가 나오든 배열의 길이가 n이라 하면 답은 1 ~ n+1 범위 안에 나오게 된다. 이 범위 밖의 숫자들은 크게 신경 쓸 필요가 없는 것이, 어짜피 해당 숫자가 나오게 되면 그만큼 기존 배열 범위 내에 등장할 숫자들이 줄어드는 것이기 때문에, 우리는 범위 내에 숫자들에 무엇이 등장했는지만 확인하고 이를 저장하면 된다. 이때도 상수 메모리 크기를 요구하지만, 배열 자체를 활용해 숫자를 표시하면 해결할 수 있다.
 우선 주어진 nums 배열을 한 번 돌며 nums 배열 범위 밖의 수(1보다 작거나, 배열의 길이보다 크거나)는 모두 -1 처리를 해준다. 그 다음엔 다시 배열을 돌며 check 함수를 호출하는데, 해당 함수는 단순 주어진 숫자(num)를 nums 배열 속에 해당 숫자가 등장함을 표시하기 위해 해당 숫자를 인덱스로 nums[num - 1]위치(1부터 n까지 표시하기 위함)에 0 표시를 해주는 함수이다. 다만 여기서 해당 위치에 표시를 해주어야 할 또 다른 숫자가 있을 수 있기에, 해당 숫자를 가지고 다시 재귀 형태로 check 함수를 호출하는 형태이다.
 그렇게 check 함수를 모두 호출하고 나면 nums 배열 속에는 숫자들이 0 혹은 그 외의 숫자들 밖 없으며, 이는 해당 인덱스 + 1의 숫자가 등장했는지 아닌지를 알려주는 배열이 된다. 이후 다시 한 번 nums 배열을 돌아 첫 번째로 0이 아닌 값이 나오게 되는 인덱스+1을 반환해주면된다. 만약 배열을 모두 돌았다면, 이는 범위 속 숫자들이 모두 등장한 것이므로 배열길이+1을 반환해주면 된다.

 

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {//우선 범위밖의 수는 -1 처리
            if (nums[i] < 1 || nums[i] > n) {
                nums[i] = -1;
            }
        }

        for (int i = 0; i < n; i++) {//탐색 후 처리
            check(nums, nums[i]);
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != 0) {
                return (i + 1);
            }
        }

        return n + 1;
    }

    void check(int[] nums, int num) {
        if (num > 0) {//주어진 값이 범위내 숫자라면
            int temp = nums[num - 1];
            nums[num - 1] = 0;
            check(nums, temp);
        }
    }
}

결과