[LeetCode # 41] First Missing Positive

정렬되지 않은 정수형 배열 nums 가 주어졌을 때, 배열에서 등장하지 않은 양의 정수 중 가장 작은 수를 찾는 문제

문제 조건으로 시간 복잡도는 O(n), 공간 복잡도는 O(1) 로 주어졌다.

 

문제에서 주어진 시간 복잡도 조건이 O(n) 이기 때문에 정렬을 하거나 하는 등의 방법은 사용이 불가능했고, 단순히 순차 탐색을 통해서만 문제를 해결해야 했다. 이 문제의 경우 풀이 방법을 고민하다가 다른 사람들의 풀이를 보고 아이디어를 얻어 문제를 풀었는데 그 아이디어는 다음과 같다.

 

문제에서 찾고자 하는 수는 nums 의 길이가 n 이라고 할 때, 1 ~ n+1 사이에 존재한다.

 

이 아이디어를 통해 생각한 풀이는, 숫자들을 순서대로 나열하면 그 중 빈 자리가 존재할 것이고, 그 위치에 있어야 하는 수가 정답이 되는 것이다. 그래서 순차적으로 배열을 탐색하고 탐색 과정에서 저장된 수들이 각자 맞는 위치에 들어가 있는 지를 확인하고 그렇지 않다면 자리를 서로 바꿔준다. 

예를 들어 [1, 2, 3, 4, 5] 는 순서대로 숫자들이 들어가 있기 때문에 자리를 바꿔줄 필요가 없지만 [1, 2, 5, 4, 3] 은 [5, 4, 3] 의 자리가 순서에 어긋나므로 [3, 4, 5] 로 변경해 [1, 2, 3, 4, 5] 의 모양을 갖도록 한다. 이렇게 1 부터 n 까지의 수가 차례대로 저장된 경우는 그 다음으로 큰 수인 n + 1 이 문제의 답이 된다. 그렇지 않고 [1, 2, 4, 5, 6] 과 같은 모양을 하게 된다면 이를 원래 자리로 숫자들을 옮기면 [1, 2, 6, 4, 5] 가 될 것이다. 왜냐하면, 6 은 이 배열의 길이 5 보다 큰 수이기 때문에 적절한 위치가 없다. 그러므로 배열 탐색 중 중간에 3이 들어가야 할 위치에 6이 들어가 있고 문제의 답은 3이 된다.

 

이러한 풀이로 작성한 코드는 다음과 같다.

 

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            // 일단 숫자가 1 ~ n 사이인 지 확인하고
            // 자기 자리 찾아주기
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};