[백준] 1958번 : LCS 3

 

LCS 문제들을 차례대로 풀고있는데

이 문제 완전 뒷통수 제대로 맞... 그냥 내가 못해서 그런거긴 한데

암튼 그래서 포스팅한다..

 

처음에는 물론 3차원 배열을 생각하기는 했다.

그런데 3차원을 .... 어떻게? 라는 생각에 에이~ 아니겠지~ 하고

첫 문자열 & 두번째 문자열 의 lcs 를 구해서 도출된 문자열과 세 번째 문자열의 LCS를 이용해서 최종 답을 도출하도록 구했다.

 

짜잔 ...~

package baekJoon.gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1958 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        String str3 = br.readLine();

        String lcsOfTwo = makeLcsStr(calculate(str1, str2), str1, str2);
        System.out.println(lcsOfTwo);
        int[][] dp = calculate(str3, lcsOfTwo);
        System.out.println(dp[str3.length()][lcsOfTwo.length()]);
    }

    static int[][] calculate(String str1, String str2) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp;
    }

    static String makeLcsStr(int[][] dp, String str1, String str2) {
        int x = str1.length();
        int y = str2.length();
        StringBuilder sb = new StringBuilder();
        while (x > 0 && y > 0) {
            if (dp[x][y] == dp[x - 1][y]) {
                x--;
            } else if (dp[x][y] == dp[x][y - 1]) {
                y--;
            } else {
                sb.append(str1.charAt(x - 1));
                x--;
                y--;
            }
        }
        return sb.reverse().toString();
    }
}

그런데 4퍼센트쯤 가서 실패를 하는거다...

 

마구잡이로 반례를 찾다보니

abcdefg

dcfogu

xdwfu

의 경우 2가 답인데 1로 나오는거다...!

 

뭔가 크게 잘못됐다는 생각을 하고 중간 LCS 문자열을 출력해봤더니

 cfg였다..

 

그제서야 전 lcs문제에서 아무 문자나 도출하라고 했던게 생각나며... LCS 문자열이 여러개일 수 있다는 생각을 하게되었다..

 

흑흑

결론은 3차원 배열을 사용하자! 이다.

 

package baekJoon.gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1958 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        String str3 = br.readLine();


        System.out.println(calculate(str1, str2, str3));
    }

    static int calculate(String str1, String str2, String str3) {
        int[][][] dp = new int[str1.length() + 1][str2.length() + 1][str3.length() + 1];
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    for (int k = 1; k <= str3.length(); k++) {
                        if (str2.charAt(j - 1) == str3.charAt(k - 1)) {
                            dp[i][j][k] = dp[i - 1][j - 1][k -1] + 1;
                        } else {
                            dp[i][j][k] = Math.max(dp[i - 1][j][k], Math.max(dp[i][j - 1][k], dp[i][j][k - 1]));
                        }
                    }
                } else {
                    for (int k = 1; k <= str3.length(); k++) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], Math.max(dp[i][j - 1][k], dp[i][j][k - 1]));
                    }
                }
            }
        }
        return dp[str1.length()][str2.length()][str3.length()];
    }

}

이렇게 했다.

코드가 지저분하다.

 

속도 향상을 위해 str1 과 str2가 다르면 str3은 검사하지 않고 str3만큼 같지 않는 처리를 해줬는데..

코드가 너저분.... ㅠ

 

뭐가 좋은 코드일까

str1.charAt(i - 1) == str2.charAt(j - 1) && str2.charAt(j - 1) == str3.charAt(k  -1)

이랑 위 코드중에..

ㅎ그흑

 

아무튼 통과..!!