23.03.21. 풀었던 문제들

Leetcode 2348. Number of Zero-Filled Subarrays

첫 접근

 [0으로 이루어진 연속된 max subarray]를 찾고, 그 subarray가 가지는 [0으로 이루어진 subarray]는 1 + 2 + ... + [해당 array length]이다.  [0으로 이루어진 연속된 max subarray]를 찾고 계산하면 늦을 것 같아 미리 1부터 n까지 합을 prefix sum으로 계산해 두었다.

 이후 탐색을 시작하며, [현 index]가 0인 경우에 더 이상 0이 아닐 때까지 i를 더해 0으로 이루어진 max subarray를 찾는다. 이후 계산한 값을 가져온다.

// Runtime 255 ms Beats 5.13%
// Memory 150.3 MB Beats 6.34%

typedef long long ll;

class Solution {
public:
    vector<ll> psum;
    void init(){
        int INF = 100001;
        psum.resize(INF);
        psum[0] = 0;
        for(int i = 1; i<INF; i++){
            psum[i] = psum[i-1] + i;
        }
    }
    long long zeroFilledSubarray(vector<int>& nums) {
        init();
        ll answer = 0;

        for(int i = 0; i<nums.size(); i++){
            ll cnt = 0;
            while(i < nums.size() && nums[i] == 0){
                i++;
                cnt++;
            }
            answer += psum[cnt];
        }

        return answer;
    }
};

 

두 번째 접근

 그런데 굳이 이렇게 풀 필요가 없다! cnt를 알고 있다면 (cnt + 1) * cnt / 2라는 등차수열 합 공식을 사용해서 쉽게 풀 수 있다. 다른 방법은, 그냥 answer에 cnt를 더해버리면 된다. 이래도 O(n)이다. 

// Runtime 162 ms Beats 86.73%
// Memory 107.5 MB Beats 86.43%

typedef long long ll;

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        ll answer = 0;

        for(int i = 0; i<nums.size(); i++){
            ll cnt = 0;
            while(i < nums.size() && nums[i] == 0){
                i++;
                cnt++;
                answer += cnt;
            }
        }

        return answer;
    }
};

 

 

세 번째 접근

 solution을 보고 안 건데. two-pointer로 풀 수도 있다.

• 2개의 pointer, i, j를 둔다.
• num[i]가 0이 아니라면 j를 i+1로 둔다.
• num[i]가 0이라면 i만 전진시킨다.
• 0의 subarray가 이어진다면 j는 0의 시작점에 있고, i는 계속 전진하고 있을 것이다. 따라서 매 연산 시 i-j+1를 한다.

 사실상 [두 번째 접근]과 동일한 풀이이다.

// Runtime 175 ms Beats 58.7%
// Memory 107.6 MB Beats 54.45%

typedef long long ll;

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        ll answer = 0;

        for(int i = 0, j = 0; i<nums.size(); i++){
            if(nums[i] != 0) j = i+1;
            answer += i - j + 1;
        }

        return answer;
    }
};

 

 

시간복잡도

 앞에서부터 뒤로 단 한 번 순회하므로 O(n)이다.

 

공간복잡도

 첫 번째 접근의 경우 모든 n에 대해 prefix sum을 저장해야 하므로 O(n)이다. 그러나 두 번째/세 번째 접근의 경우 별도의 저장공간을 사용하지 않기 때문에 O(1)이다.