23.04.22. 풀었던 문제들

Leetcode 1312. Minimum Insertion Steps to Make a String Palindrome

 longest palindrome subsequence length(x라고 하자)를 알아내면 되는 문제이다.
 왜냐하면, 전체 길이를 n이라 할 때, n - x를 하면 되기 때문이다.longest palindrome subsequence는 이미 palindrome이기 때문에 나머지 부분인 n - x인 부분만만 채워 넣으면 palindrome이 되기 때문이다.

 그렇다면 쉬운 문제다. longest palindrome subsequence를 찾는 건 LCS와 유사한 DP로 쉽게 풀 수 있다.

 

 dp[i][j]를 index i to j까지 longest palindrome subsequence length로 정의하면 아래와 같다.

• s[i] == s[j] then dp[i][j] = dp[i+1][j-1] + 2 / else max(dp[i][j-1], dp[i+1][j]
• 거꾸로는 dp[i-1][j+1] = dp[i][j] + 2 when s[i-1] == s[j+1] / else dp[i-1][j+1] = max(dp[i-1][j], dp[i][j+1])

 이 두 식 중에 구현하기 편리한 것은 위의 것이다. 아래 것은 범위를 신경써 주어야 하기도 하고 여러 번 연산해 줘야 하는 반면 위의 것은 원큐에 dp[i][j]를 바로 계산할 수 있기 때문이다.

 

 base case는 아래와 같다.

• dp[i][i] = 1 for all i

 

첫 번째 접근 : bottom-up DP

 DP 문제를 풀며 느낀 건데, 가능하면 for문을 사용하는 bottom-up과 recurse를 사용하는 top-down 모두에 익숙해여야 하는 것 같다. 그래서 이 문제부터는 두 가지 방식으로 풀려 한다.

 사실 이 문제는 몇 번 풀어본 문제라 좀 쉽게 풀었다. 특히 대각선 접근은 distance를 1부터 n까지 설정하고, i값으로 for문을 돌린 후 j값을 만들어 주는 게 제일 직관적이고 빠르고 이상적인 것 같다. 이제부터 이렇게 쓰려 의식해 보자.

class Solution {
public:
    int minInsertions(string s) {
        int n = s.length();
        // dp[i][j] : index i to j까지 max palindrome subsequence length
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(int i = 0; i<n; i++) dp[i][i] = 1;

        for(int d = 1; d<n; d++){
            for(int i = 0; i<n-d; i++){
                int j = i+d;
                if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
                dp[i][j] = max(dp[i][j], max(dp[i+1][j], dp[i][j-1]));                
            }
        }

        return n - dp[0][n-1];
    }
};

 

 

두 번째 접근 : top-down DP

 recurse 사용하는 게 항상 귀찮고, 어렵다. 종료조건 설정하는 게 까다로워서...

 일단 재귀 식은 동일하다. 그리고 top-down dp는 함수 자체가 DP의 정의를 나타내기 때문에 좀 더 직관적?인 부분도 있긴 하다. 

 여기서 종료 조건은 크게 3가지이다.

• memoization이 된 경우(이미 탐색한 경우)
• i == j인 경우 return 1
• i > j인 경우 return 0

 위 3가지 경우를 제외한 경우에는 점화식을 따라 탐색하면 된다.

class Solution {
public:
    int recurse(vector<vector<int>> &dp, string &s, int i, int j){
        if(dp[i][j] != 0) return dp[i][j];
        if(i == j) return 1;
        if(i > j) return 0;
        if(s[i] == s[j]){
            dp[i][j] = recurse(dp, s, i+1, j-1) + 2;
            return dp[i][j];
        }
        else{
            dp[i][j] = max(recurse(dp, s, i+1, j), recurse(dp, s, i, j-1));
            return dp[i][j];
        }
    }
    int minInsertions(string s) {
        int n = s.length();
        // dp[i][j] : index i to j까지 max palindrome subsequence length
        vector<vector<int>> dp(n, vector<int>(n, 0));

        return n - recurse(dp, s, 0, n-1);
    }
};

 

시간복잡도

 n by n size의 2D array를 순회하며 탐색하므로 O($n^2$)이다.

 

공간복잡도

 n by n size의 2D array를 정의하고 탐색하므로 O($n^2$)이다. top-down의 경우 worst case stack이 O(n)만큼 쌓인다.

 

후기

 top-down에 익숙해지자.