꿀잠

https://leetcode.com/problems/regular-expression-matching/description/

주어진 문자열이 패턴에 맞는 문자열인지 확인하는 문제이다. 주어지는 패턴은 '.' 일 경우 같은 모든 문자에 대칭 되고, '*' 일 경우 앞 글자 하나와 함께 묶여 해당 문자가 여러 개 가능하다는 뜻이다. DP로 해결이 가능하고 이전에 풀었던 다른 문제들의 경험 덕분에 풀 수 있었다. 아래의 두 문제와 점화식을 만들어 가는 방식이 비슷하다.

https://leetcode.com/problems/edit-distance/description/
https://ygs3004.tistory.com/97

https://leetcode.com/problems/longest-common-subsequence/description/
https://ygs3004.tistory.com/78

각 문자의 부분 문자열을 기반으로 DP 배열의 초기화와 점화식을 세워줄 수 있다. 특정 문자열 s의 인덱스 j 와 패턴 p의 문자열 i일 때를 생각해 보자. "." 또는 각 문자가 해당 인덱스에서 같을 경우 dp 배열의 true,false 값은 (i - 1)(j - 1)의 값과 같다. 왜냐하면 각 글자가 추가 되기 전에 같았다면 새로운 글자가 똑같이 생긴 경우이기 때문이다. 그리고 각 글자가 다를 경우 당연히 false가 된다.

별이 있는 패턴의 경우 해당 패턴의 i - 1 일 때의 값이 참인 경우에 참이 된다. 패턴의 새로운 문자열과 별개로 참이기 때문이다. 또한 j - 1 이 참일 경우 별문자의 문자값과 j의 문자값이 같을 경우 참이 된다. 그 이전까지의 문자가 패턴에 부합할 때 별 문자의 문자 새로 생겼다고 판단할 수 있기 때문이다. 아래에 임의의 값을 가지고 True, False 값을 찾아가는 배열을 만든 경우이다. i인 row가 늘어나는 경우를 패턴, j인 col이 늘어나는 경우가 문자열을 나타낸다.

확인해 보아야 하는 관계는 각 글자가 같을 때 (i - 1). (j - 1)의 값을 참조 해야 한다는 것, 별패턴일 경우엔 (i - 1)의 값과 문자가 같을 때 (j - 1)의 값을 참조 해야 한다는 점이다.

해당 규칙을 이용해서 최종적으로 통과한 코드는 아래와 같다. 별표의 경우 문자 + 별로 두 글자의 인덱스를 차지하므로 대문자로 치환하여 비교문을 작성했다.

public class Solution {  
    public boolean isMatch(String s, String p) {  
  
        final String dotStar = String.valueOf((char)('a' - 1));  
  
        // * + 문자를 대문자로, . 일 경우 dotStar로 치환(char < 'a'로 부등호로 비교하기 위하여)  
        while(p.indexOf("*") > - 1){  
            int starIdx = p.indexOf("*");  
            String starChar = String.valueOf(p.charAt(starIdx - 1)).toUpperCase();  
            starChar = starChar.equals(".") ? dotStar : starChar;  
            p = p.substring(0, starIdx - 1) + starChar + p.substring(starIdx + 1);  
        }  
  
        boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];  
        dp[0][0] = true;  
  
        for(int i = 1; i < dp.length; i++){  
            dp[i][0] = (p.charAt(i - 1) != '.') && (p.charAt(i - 1) < 'a') && dp[i - 1][0];  
        }  
  
        for(int i = 1; i < dp.length; i++){  
            char char1 = p.charAt(i - 1);  
            for(int j = 1; j < dp[0].length; j++){  
                char char2 = s.charAt(j - 1);  
                if(char1 == '.' || (char1 == char2)){  
                    dp[i][j] = dp[i - 1][j - 1];  
                }else if(char1 < 'a'){  
                    dp[i][j] = dp[i - 1][j] || (dp[i][j - 1]  
                            && (char1 == (char)('a' - 1) // dotStart일 경우  
                                || ((char1 + ('a' - 'A')) == char2))); // 대문자일 경우  
                }else{  
                    dp[i][j] = false;  
                }  
            }  
        }  
  
        return dp[p.length()][s.length()];  
  
    }  
  
}

https://leetcode.com/problems/burst-balloons/description/

풍선을 터트리는 순서에 따라 얻는 점수가 다를 때 가장 크게 점수를 얻을 수 있는 방법에 대해 묻는 문제이다. DP 문제로 아이디어를 열심히 생각해 보았지만 잘 떠오르지 않아 해당 문제의 팁을 찾아보고 통과할 수 있었다.

풍선을 터트렸을 때 얻는 점수는 양쪽 좌우 잔여 풍선이 어떤지에 따라 다르다. 이 문제의 점화식의 아이디어는 특정 풍선을 터트릴 때 좌우로 구간이 나뉘며 문제를 작게 볼 수 있다는 점이다.

1 2 3 4 5 의 풍선이 있을 때 3을 터트릴 경우
1 2 - 3 - 4 5 문제를 3구간으로 나눌 수 있다.
1 2 구간의 최대 가능 점수, 3을 터트렸을 때의 점수, 4 5 구간의 최대 가능 점수이다.

이러한 사실을 이용해서 점화식을 세우고, 큰 구간의 점수를 계산하기 위해서 작은 구간의 최대 점수부터 차례대로 큰 구간의 점수를 찾아가는 형태의 순회를 해야 한다. 또한 주어진 조건에 따라 기본 풍선 점수 표 양 끝에 1점의 임의 점수를 추가해주면 문제를 코드를 작성하기에 편의성이 생긴다. 이러한 점들을 고려하며 통과한 최종 코드는 아래와 같다.

public class Solution {  
    public int maxCoins(int[] nums) {  
        int[] arr = new int[nums.length + 2];  
        for(int i = 0; i < nums.length; i++){  
            arr[i + 1] = nums[i];  
        }  
        arr[0] = 1;  
        arr[arr.length - 1] = 1;  
        int n = arr.length;  
  
        int[][] dp = new int[n][n];  
  
        for(int k = 0; k < n - 2; k++){  
            for(int l = 1; l + k <= n - 2; l++){  
                int r = l + k ;  
                for(int j = l; j <= r; j++){  
                    int front = dp[l][j - 1];  
                    int shoot =  arr[l - 1] * arr[j] * arr[r + 1];  
                    int back = dp[j + 1][r];  
  
                    dp[l][r] = Math.max(dp[l][r], front + shoot + back);  
                }  
            }  
        }  
  
        return dp[1][n - 2];  
    }  
  
}

https://leetcode.com/problems/edit-distance/

이번 문제는 DP 문제로 1번 문자열을 2번 문자열로 변환 시킬 때 삽입,삭제,대체 의 세가지 기능을 이용하여 최소 몇 번으로 변화 시킬 수 있는지 묻는 문제이다. DP 문제라는 것을 알고도 아이디어가 떠오르지 않아 한참 고민하다 결국 정답 영상을 찾아 보고야 말았다. 정답을 확인하고 나니 이전에 풀었던 최대 부분 문자열 찾기 문제랑 흡사한 형태였다. 해당 문제는 아래에 있다.

https://leetcode.com/problems/longest-common-subsequence/

이 문제를 풀이 이해하기 위해선 DP 배열 표를 만들어 보면 이해하기 쉽다. 문제에 주어진 예제중 하나인 horse 와 ros 를 기준으로 예외 표를 아래와 같이 그릴 수 있다.

각 좌표에서의 값을 분석해보자 우선 1행과 1열의 값을 보자.
빈 문자열에서 h, ho, hor, hors, hosrse 의 문자열을 만들기 위해선 삽입이란 행동이 필요하므로 1씩 증가한다. 마찬가지의 원리로 1열 또한 증가한다. 임의의 행, 열에서 각각의 행 문자와 열 문자가 같다면 i - 1, j - 1의 값과 같다. 예를 들어 hors 와 ros 의 최소 변환 값은 hor과 ro의 변환 값과 같다. 마지막 s는 변환이 필요 없기 때문이다. 따라서 i - 1, j - 1인 hor, ro의 값과 같다는 점을 알 수 있다.

한편 행과 열의 추가 문자가 다른 경우를 보자 ho와 r의 경우 2이다. 이 경우는 h, r 에서 o를 삭제하는 행위가 추가되는 경우이고, , h,""의 경우의 수에 o를 r로 대체하는 경우의 수가 추가되는 경우이다. 이처럼 i - 1의 경우 삽입의 경우의 수가 늘어나고, j - 1 의 경우 삭제의 경우의 수가 늘어나는 경우, 그리고 i - 1, j - 1 의 경우 대체의 경우의 수가 늘어나는 경우이다.

특정 i, j 에서 글자 수가 생성된다면 이 경우의 수에 한 번의 삽입, 삭제, 대체로 변환 시킬 수 있다. 따라서 최소 변환 방법은 (i, i - 1), (j, j - 1), (i - 1, j - 1)의 값 중에서 가장 작은 값에 1을 추가 시킨 경우이다. 이를 이용하여 점화 식을 만들어 해결하면 아래와 같은 코드가 나온다.

 public class Solution {  
    public int minDistance(String word1, String word2) {  
        int m = word1.length() + 1;  
        int n = word2.length() + 1;  
  
        int[][] dp = new int[m][n];  
  
        for(int i = 0; i < m; i++){  
            dp[i][0] = i;  
        }  
  
        for(int j = 0; j < n; j++){  
            dp[0][j] = j;  
        }  
  
        for(int i = 1; i < m; i++){  
            char c1 = word1.charAt(i - 1);  
            for(int j = 1; j < n; j++){  
                char c2 = word2.charAt(j - 1);  
                if(c1 == c2){  
                    dp[i][j] = dp[i - 1][j - 1];  
                }else{  
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;  
                }  
            }  
        }  
  
        return dp[m - 1][n - 1];  
    }  
}

https://leetcode.com/problems/longest-common-subsequence/description/

두 문자열의 가장 긴 부분 문자열의 길이를 구하는 문제이다. 부분 문자열이란 말의 개념이 처음에는 혼돈이 와서 정답을 제출하면서 테스트 케이스들을 확인하고 진행하였다.

부분 문자열이란 두 전체 문자열을 이루는 문자들의 순서와 구성이 동일한 문자열을 말한다. 단 이때 전체 문자열에서 다른 문자가 있더라도 순서만 맞으면 된다.

1."ascne"
2."abdcet"

위의 두 문자가 있다면 최대 길이 부분 문자열은 "ace" 이다 ace 는 두 문자열을 이루는 문자에 순서대로 들어가며, 양쪽에 다 포함되기 때문이다.

문제를 이해하고 나서 풀이 방식이 떠오르지 않았지만 알고리즘 카테고리가 DP라는 것을 인지하고 나서는 풀이를 진행할 수 있었다. 만약 카테고리가 없었다면 혼자 풀기는 힘들었을 것 같다. 점화식의 아이디어는 두 문자열을 비교하는 것으로 시작한다.

1. 특정 인덱스의 두 문자열을 비교했을 때 두 문자열이 같다.
   ->두 문자열의 현재 인덱스 -1일 때의 최대 부분 문자열의 크기에서 1증가
2. 특정 인덱스의 두 문자열을 비교했을 때 두 문자열이 같다
   -> 두 문자열 인덱스 -1일 때 비교했을 때랑 최대 부분 문자열의 크기와 같음

인덱스 - 1 의 값을 처리해야 하므로 dp 배열의 크기를 +1 해주고 문자를 추출할 때는 -1 해서 문제를 해결해주었다. dp 배열의 마지막 행열 값이 문자열의 모든 문자를 확인한 값으로 최종 정답이 된다.

public class Solution {  
    public int longestCommonSubsequence(String text1, String text2) {  
  
        int text1Length = text1.length();  
        int text2Length = text2.length();  
  
        int[][] dp = new int[text1Length + 1][text2Length + 1];  
  
        for(int i = 1; i <= text1Length; i++){  
            char c1 = text1.charAt(i - 1);  
            for(int j = 1; j <= text2Length; j++){  
                char c2 = text2.charAt(j - 1);  
                if(c2 == c1){  
                    dp[i][j] = dp[i][j] = dp[i-1][j-1] + 1;  
                }else{  
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);  
                }  
            }  
        }  
  
        return dp[text1Length][text2Length];  
    }  
}