[LeetCode] 516. Longest Palindromic Subsequence - 동적계획법(Dynamic Programming) + 깊이우선탐색(DFS) + 문자열(String) JAVA

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

코드설명

동적계획법(Dynamic Programming) + 깊이우선탐색(DFS) + 문자열(String) 을 활용합니다.

 

처음에 Palindromic Subsequence이기에 가운데에서 팰린드롬을 판단하면서 처리하려고 했습니다. 하지만, 이 문제의 경우 Subsequence로써 문자열을 언제든지 자를 수 있는 것을 의미하므로 굳이 가운데에서부터 처리할 필요가 없었습니다.

 

양 옆에서 다가오면서 모든 경우를 탐색하고, 중복 연산은 동적계획법으로 Cache 처리합니다.

 

구현에 있어서 어려웠던 점은, DFS를 통해 기저사례에서 left와 right가 다른경우를 처리하게 되었는데, 이 과정에서 for문을 사용하게 되고, 구현이 제대로 작동되지 않았습니다.

 

그 대신에 아래와 같이 현재 left와 right가 일치할경우에만 개수를 증가시킨다는 생각으로, 일치한다면 개수를 1 증가시키고, 재귀함수를 계속해서 호출해나가서 완전탐색으로 처리합니다.

//비교를 여기서 처리합니다. 기저사례에서 처리하는 것보다는 재귀실행 전 처리해야 로직이 간단해집니다.
if(S.charAt(left) == S.charAt(right)){
    first = DFS(left - 1, right + 1) + 1;
}

항상 다음 위치를 기반으로 처리한뒤, 재귀함수를 실행하는 구조에 익숙해져서 위와 같이 현재 위치를 처리하고, 개수를 세는 방식을 놓쳤던 것 같습니다. 이러한 구조는 frist = DFS(left - 1, right + 1) + 1; 처럼 현재 함수가 실행시 +1 을 현재 재귀레벨에서 처리하기에, 이것도 결국에는 다음 재귀의 기저사례에서 처리하는 것과 똑같습니다.

 

코드

정답코드2입니다. 양쪽끝에서 출발하여 처리한 코드입니다. 

class Solution {
    String S;
    int[][] cache = new int[1001][1001];
    public int longestPalindromeSubseq(String s) {
        S = s;
        int answer = 0;   
        for(int[] v : cache) Arrays.fill(v, -1);

        return DFS(0, S.length() - 1);
    }
    int DFS(int left, int right){
        if(left > right) return 0;
        if(left == right) return 1;
        if(cache[left][right] != -1) return cache[left][right];
        int ret = 0;
        if(S.charAt(left) == S.charAt(right)){
            ret = DFS(left + 1, right - 1) + 2;
        }
        else if(S.charAt(left) != S.charAt(right)){
            int ret1 = DFS(left + 1, right);
            int ret2 = DFS(left, right - 1);
            ret = Math.max(ret1, ret2);
        }

        return cache[left][right] = ret;
    }
}

 

DFS함수 호출시 아래의 조건문을 활용하여 먼저 체크하고 함수를 호출함으로써 현재위치를 판단하고 넘어갑니다.

if(S.charAt(left) == S.charAt(right)){

정답코드1입니다. 하지만, DFS(i, i), DFS(i, i+1)처럼 모든 경우를 완탐하면서 DP를 적용하므로 통과는 하지만, 속도가 느립니다.

class Solution {
    String S;
    int[][] cache = new int[1001][1001];
    public int longestPalindromeSubseq(String s) {
        S = s;
        int answer = 0;   
        for(int[] v : cache) Arrays.fill(v, -1);
        for(int i=0; i<S.length(); i++){
            int first = DFS(i, i);
            int second = DFS(i, i + 1);
            answer = Math.max(answer, Math.max(DFS(i, i), DFS(i, i + 1)));
        }
        return answer;
    }

    int DFS(int left, int right){
        if(left < 0 || right >= S.length()) return 0;
        if(cache[left][right] != -1) return cache[left][right];
        int first = 0, second = 0, third = 0;

        if(left == right){
            //비교를 여기서 처리합니다. 기저사례에서 처리하는 것보다는 재귀실행 전 처리해야 로직이 간단해집니다.
            if(S.charAt(left) == S.charAt(right)){
                first = DFS(left - 1, right + 1) + 1;
            }
        }else if(left < right){
            if(S.charAt(left) == S.charAt(right)){
                first = DFS(left - 1, right + 1) + 2;
            }
            if(S.charAt(left) != S.charAt(right)){
                first = DFS(left - 1, right);
                second = DFS(left, right + 1);
            }
        }
        return cache[left][right] = Math.max(first, second);
    }  
}

처음에 틀린 방식입니다. DFS만으로 해결하다가, for문이 섞이게 되면서 접근이 틀렸습니다.

class Solution {
    String S;
    public int longestPalindromeSubseq(String s) {
        S = s;
        int answer = 0;
        for(int i=0; i<s.length(); i++){
            System.out.println("===================== i:"+i+"i+1:"+(i+1));
            System.out.println(DFS(i, i));
            System.out.println(DFS(i, i + 1));
            answer = Math.max(answer, Math.max(DFS(i, i), DFS(i, i + 1)));
        }
        return answer;
    }

    int DFS(int left, int right){
        if(left < 0 || right >= S.length()) return 0;
        // if(S.charAt(left) != S.charAt(right)) return 0;
        int ret = 0, leftJump = 0, rightJump = 0, noJump = 0;

        if(left == right) {
            noJump = DFS(left - 1,right + 1) + 1;
            for(int i=left - 1; i>=0; i--){
                if(S.charAt(i) == S.charAt(right))
                    leftJump = Math.max(leftJump, DFS(i, right) + 1);
            }
            for(int i=right + 1; i<S.length(); i++){
                if(S.charAt(left) == S.charAt(i))
                    rightJump = Math.max(rightJump, DFS(left, i) + 1);
            }
        }
        else {
            for(int i=left - 1; i>=0; i--){
                if(S.charAt(i) == S.charAt(right))
                    leftJump = Math.max(leftJump, DFS(i, right) + 1);
            }
            for(int i=right + 1; i<S.length(); i++){
                if(S.charAt(left) == S.charAt(i))
                    rightJump = Math.max(rightJump, DFS(left, i) + 1);
            }
            leftJump = DFS(left - 1, right) + 0;
            rightJump = DFS(left, right + 1) + 0;
            noJump = DFS(left - 1, right + 1) + 2;
            //3. 왼족오른쪽 삭제는 1번과 2번 실행시 자동으로 커버링됨.
        }
        return ret + Math.max(leftJump, Math.max(rightJump, noJump));
    }
}