[LeetCode] Kth Missing Positive Number

https://leetcode.com/problems/kth-missing-positive-number/description/

Kth Missing Positive Number - LeetCode

 

난이도 Easy로 구현 자체는 상당히 쉬운 문제입니다. Blind75, Grind75에 속하진 않지만 우연히 발견해 풀어봤습니다.

 

03/07

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        vector<bool> allNum(2001);
        int cnt = 0;
        for(int i = 1; i < 2001; ++i) allNum[i] = 1;
        for(int num : arr) allNum[num] = 0;
        for(int i = 1; i < 2001; ++i){
            if(allNum[i]) ++cnt;
            if(cnt == k) return i;
        }
        return -1;
    }
};

 

위 풀이에서 주목할 점은 allNum의 자료형이 vector<bool>이라는 점입니다. 만약 bool allNum[2001];로 정의한다면 시간이 상대적으로 느려질 수 있습니다. bool은 true, false를 저장하는 자료형으로 그 크기는 1byte입니다. 그런데 vector<bool>로 두면 각 bool 한 칸이 1byte가 아니라 1bit만 차지하도록 최적화가 이루어 집니다. 이로 인해 memory도 8배 적게 쓰고 cache hit rate이 올라가서 시간도 빨라지게 됩니다. 큰 차이는 아니지만 알아두면 좋은 내용 같아서 공유합니다. ( Reference : https://blog.encrypted.gg/983) 

 

이런 간단해 보이는 문제를 업로드한 이유는 다름 아닌 문제 하단의 Follow-up question에 있습니다. 

Could you solve this problem in less than O(n) complexity?

상기 제 풀이는 시간복잡도도 O(N), 공간복잡도도 O(N)입니다. 하지만 위 질문에서 확인할 수 있듯 최적화가 가능합니다.

다음은 시간복잡도 O(logN), 공간복잡도 O(1)의 알고리즘입니다.

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = arr.size();
        int left = 0, right = n-1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (arr[mid] - (mid + 1) < k)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left + k;
    }
};

이 문제에서는 N이 워낙 작아 앞선 풀이가 더 빠르게 수행되지만 N이 10억 정도로 커진다면 첫 번째 O(N) 알고리즘은 사용할 수 없지만 두 번째 O(logN) 알고리즘은 빠르게 수행될 수 있습니다. (일반적으로 time limit은 1초, space limit은 512MB인 것을 고려했을 때)