23.04.16. 풀었던 문제들

Leetcode 1639. Number of Ways to Form a Target String Given a Dictionary

 DP 문제. 처음에 이해를 잘못해서 어렵게 푼 문제...

 

 words가 [abbac, eabbc, abbbc]와 같이 주어졌을 때 아래처럼 정렬해 보자.

• abaac
• eabbc
• abbbc

 

 이렇게 두고, 만약 words[1][1]의 a를 골랐다고 하면 모든 word에 대해 index 1 이하인 것은 사용할 수 없다.

• ab / aac
• ea / bbc
• ab / bbc

 

 이렇게 생각하면 words의 어떤 column j을 이용해 target[i]를 만들 수 있는지 여부를 판단하면 될 것 같다. 따라서, dp[i][j] : substring j까지 ith col 이용해 만드는 경우의 수라고 두자. 그러면

• ith col에 있는 char 사용하는 경우 : dp[i][j] * ith col의 target[j] 개수
• ith col에 있는 char 사용하지 않는 경우 : dp[i][j+1]

가 된다. 구현의 편의성을 위해 j = 0인 col의 모든 값은 0으로 두고, i = 0인 row는 모두  1로 두자. (i=0은 곱 계수를 1로 만들기 위함). 추가로 ith col의 target[j] 개수를 따로 저장하자. 그러면 쉽게 풀린다!

// Runtime 332 ms Beats 47.42%
// Memory 79.1 MB Beats 31.90%

typedef long long ll;

class Solution {
public:
    int MOD = 1e9 + 7, T, W, S;
    int numWays(vector<string>& words, string target) {
        T = target.size(), W = words.size(), S = words[0].size();
        vector<vector<int>> cnt(S, vector<int>(26, 0)); // cnt[i] : 모든 words들의 ith index의 char 개수
        for(int i = 0; i<W; i++){
            for(int j = 0; j<S; j++){
                cnt[j][words[i][j] - 'a']++;
            }
        }

        vector<vector<ll>> dp(S+1, vector<ll>(T+1));
        // dp[i][j] : substring j까지 ith col 이용해 만드는 경우의 수
        // ith col에 있는 char 사용하는 경우 dp[i][j] * ith col의 target[j] 개수
        // ith col에 있는 char 사용하지 않는 경우 dp[i][j+1]

        for(int i = 0; i<S; i++){
            dp[i][0] = 1;
            for(int j = 0; j<T; j++){
                dp[i + 1][j + 1] = ((cnt[i][target[j] - 'a'] * dp[i][j]) % MOD + dp[i][j + 1]) % MOD;
            }
        }

        return dp[S][T];
    }
};

 

시간복잡도

 target size를 T, words size를 W, word size를 S로 했을 때 W * S를 한 번, S * T를 한 번 순회하므로 O(S(W + T))이다.

 

공간복잡도

 S size vector, S * T size dp vector를 만드므로 O(ST)

 

후기

 솔직이 이 문제는 내가 졌다. 어제 문제도 그렇고... DP 너무 약한 것 같다. DP 할 때 항상 고민되는 것

• top-down vs bottom-up
• 이전 state s-1, 현 state s, 다음 state s+1이 있을 때, s-1을 이용해 s를 계산할지 vs s를 이용해 s+1을 계산할지

가 항상 고민이다. 이거 한끗 차이로 코드가 짧아지고 길어지고 해서... 근데 문제마다 다른 설정값을 가지고 있어서 어떤 게 optimal인지 항상 너무 어렵다. 노력밖에 답이 없다... 많이 풀어보자. 자신감 많이 깎이는군.