23.05.06. 풀었던 문제들

Leetcode 1498. Number of Subsequences That Satisfy the Given Sum Condition

 일단 이 문제를 brute-force로 푼다면, length n인 것들에 대해 모든 subset을 봐야 하므로 $2^n$ 개수를 보아야 한다. 그러나 n이 100,000이기 때문에 시간 초과가 무조건 난다. 다른 방법을 풀어야 한다.

 

 이 문제는 two-pointer로 푸는 문제이다.

 만약 array가 정렬된 상태에서 어떤 subarray를 골랐다고 치자. 정렬된 상태이므로 subarray의 첫 번째 index, 마지막 index element만 가져와서 target의 값과 비교하면 된다. 그 합이 target보다 작다면 해당 subarray의 모든 subset은 문제 조건을 만족하는 답이 된다. 이게 첫 번째

 다음 접근을 생각해 보자. two-pointer로 해당 subarray를 골라낼 수 있을 것이다. subarray를 고르고, 첫 번째 element를 무조건 넣는다고 생각하면 중복도 발생하지 않을 것이다. 따라서 two-pointer로 arr[left], arr[right]보다 target이 작은 subarray에 대해 2^k를 수행하면 된다.

// Runtime 141 ms Beats 55.87%
// Memory 49.8 MB Beats 58.53%

class Solution {
public:
    int MOD = 1e9 + 7;
    int numSubseq(vector<int>& nums, int target) {
        int len = nums.size(), left = 0, right = len - 1;
        sort(nums.begin(), nums.end(), less<int>());
        
        // for efficiency, pre-calculate pow of 2's
        vector<int> pows(len);
        pows[0] = 1;
        for(int i = 1; i<len; i++){
            pows[i] = (2*pows[i-1]) % MOD;
        }

        int answer = 0;
        while(left <= right){
            if(nums[left] + nums[right] <= target){
                answer = (answer + pows[right - left]) % MOD; // nums[left]를 포함하고, left + 1부터 right까지 subset에 nums[left]를 합치면 문제 조건에 인정됨.
                left++;
            }
            else{
                right--;
            }
        }
        return answer;
    }
};

 

시간복잡도

 two-pointer를 사용하므로 O(n)이다.

 

공간복잡도

 $2^k$에 대한 것을 저장하므로 O(n)의 추가 공간이 필요하다.

 

후기

 까다롭다.