23.04.23. 풀었던 문제들

1416. Restore The Array

 일단 문제 조건이 n = 100000이므로 O(n)으로 풀어야 하는 문제이다. 따라서 1D array dp[i]를 둔다.

 처음엔 dp[i]를 0부터 i까지 만들 수 있는 경우의 수로 생각하려 했는데 그러면 dp[i+1]을 구하기 까다로워 거꾸로 정의했다.

• dp[i] : i부터 n까지 가능한 경우의 수라고 정의

 그러면 다음으로 점화식을 세워야 한다. 처음에는 i부터 k length만큼 전진하고, 각 단계에서 number를 만들고 k와 비교하려 했다. 그런데 그러면 k와 비교하는 로직이 중복되어서 숫자를 만들고, 숫자가 k보다 작으면 더하는 게 구현하기 편할 것 같았다.

 일단 dp[i]를 계산하기 위해 i부터 substring을 만들고, 이 때 substring이 k 이하가 되도록 만들어야 한다.
 예를 들어 s = 1317, k = 10000이라면, dp[0]을 계산하기 위해

• substring 1 + [317를 분할하는 경우의 수]
• substring 13 + [17를 분할하는 경우의 수]
• substring 131 + [7를 분할하는 경우의 수]
• substring 1317 + [를 분할하는 경우의 수]
• 들의 합을 계산해 주어야 한다. []는 해당 문자열의 계산 결과.

 이 때 substring이 k보다 크다면 거기서 멈춰 주어야 할 것이다. 예를 들어 k = 130이었다면 위 2개 경우만 계산해야 했을 것이다.

즉, 위 예시에서는

• dp[4] = 1 (base case)
• dp[3] = dp[4] = 1
• dp[2] = dp[3] + dp[4] = 1 + 1 = 2
• dp[1] = dp[2] + dp[3] + dp[4] = 2 + 1 + 1 = 4
• dp[0] = dp[1] + dp[2] + dp[3] + dp[4] = 4 + 2 + 1 + 1 = 8

 그러면, dp[i-1] = dp[i] + dp[i+1] + ... + dp[i+logk]이고, dp 항 하나당 최대 logk만큼 for문이 돈다. 이 때, substring이 k보다 작게 만들어야 한다.

 base case는 ""를 분할하는 경우가 되므로 i == n일 때 경우의 수 1이 될 것이다. (substring으로만 이루어진 집합)

Top-down DP

// Runtime 73 ms Beats 56.98%
// Memory 22 MB Beats 18.60%

typedef long long ll;

class Solution {
public:
    int n, MOD = 1e9+7;
    int recurse(string& s, int k, vector<int>& dp, int i){
        if(i == n) return 1; // base case
        if(dp[i] != -1) return dp[i];
        if(s[i] == '0') return 0;
        
        ll result = 0;
        ll createdNumber = 0;
        // i를 시작점으로 k까지 늘려가며 숫자를 만듬
        for(int j = i; j<s.length(); j++){
            createdNumber = 10 * createdNumber + s[j] - '0';
            if(createdNumber > k) break;
            result = (result + recurse(s, k, dp, j+1)) % MOD; // *** 탐색 가능하다면 그 값 더함
        }
        dp[i] = result;
        return dp[i];
    }
    int numberOfArrays(string s, int k) {
        n = s.length();
        // dp[i] : i부터 n까지 가능한 경우의 수
        vector<int> dp(s.length(), -1);

        return recurse(s, k, dp, 0);
    }
};

 

Bottom-up DP

 bottom-up의 경우에도 top-down과 점화식이 동일하기에 똑같이 풀 수 있다. 같은 base case를 두고, 같은 종료 조건을 두고, 같은 점화식을 사용해 풀면 된다.

// Runtime 36 ms Beats 95.93%
// Memory 11.8 MB Beats 86.5%

class Solution {
public:
    int numberOfArrays(string s, int k) {
        int MOD = 1e9+7;
        int n = s.length();
        vector<int> dp(n+1, 0);
        dp[n] = 1; // base case

        ll result, createdNumber;
        for(int i = n-1; i>=0; i--){ // *** dp[i]는 i보다 큰 j에 대해 dp[j]에 depend하므로 n-1부터 0까지 순서로 계산해야 함
            if(s[i] == '0') continue;
            result = 0; createdNumber = 0;
            // i를 시작점으로 k까지 늘려가며 숫자를 만듬
            for(int j = i; j<n; j++){
                createdNumber = 10 * createdNumber + s[j] - '0';
                if(createdNumber > k) break;
                result = (result + dp[j+1]) % MOD; // *** 탐색 가능하다면 그 값 더함
            }
            dp[i] = result;
        }
        return dp[0];
    }
};

 

 단 function stack이 덜 쌓이므로 확실히 시간과 메모리 측면에서 많은 이득을 본 것을 볼 수 있다.

 

 

시간복잡도

 dp[i-1] = dp[i] + dp[i+1] + ... + dp[i+logk]이고, dp 항 하나당 최대 logk만큼 for문이 돈다. k = $10^9$이고 n = $10^5$이므로 로 O(nlogk)이고, logk는 worse case 9이므로 90만이 된다. 시간 안에 충분히 풀 수 있다.

 

공간복잡도

 n size dp vector를 하나 만들고, recurse도 항상 O(n)만큼 쌓이므로 O(n)이다.