[BOJ 9252] LCS 2 - JAVA, Gold4

https://www.acmicpc.net/problem/9252

9252번: LCS 2

풀이

사용한 알고리즘 : LCS (Longest Common Subsequence)

 

풀이전략

LCS란 최장 공통 부분집합으로 문자열 X, Y가 주어졌을 때,

X와 Y에서 공통으로 나타나는 부분 문자 집합 중 길이가 최대가 되는 부분 집합을 의미한다.

 

예로 X = ACAYKP

Y = CAPCAK 라고 할 때,

 

두 문자열의 LCS 는 ACAK이다.

 

만약 완전 탐색기법을 사용하여 각 문자열이 가질 수 있는 모든 부분집합을 비교하게 되면

시간 복잡도가 O(2^n)이 발생한다.

 

이유는 길이가 m인 하나의 문자열에서 모든 부분 집합의 개수는 2^m 개인데

문자열 X의 길이가 m, 문자열 Y의 길이가 n이라고 할 때,

두 부분집합을 모두 비교하는 연산의 시간 복잡도는 O(2^m * 2^n) = O(2^(n+m)) = O(2^n)이기 때문이다.

 

n은 최대 1000까지 주어진다고 했으므로

시간 복잡도가 최악의 경우에 2^1000 = 1.07150860718626732094842504906e+301 으로

어마어마한 수가 나와 시간 초과가 발생한다.

 

따라서 완전 탐색의 방법으로는 제한 시간 내에 풀 수 없고

동적 계획법을 적용하여 문제를 보다 효율적으로 풀이해야 한다.

 

아래 배열은 X = ABCBDAB, Y = BDCABA 라는 문자열이 주어졌을 경우

LCS를 구하는 과정에 필요한 배열이다.

만약 X.getChar(i) == Y.getChar(j) 라면 d[i][j] = d[i-1][j-1] +1 이고
X.getChar(i) != Y.getChar(j) 라면 d[i][j] = Math.max(d[i-1][j], d[i][j-1]) 이다.

이유는 배열 d 내부 각각의 원소는, 해당 인덱스에서 가질 수 있는 LCS의 길이를 나타내는데,
X.getChar(i) == Y.getChar(j)인 경우 동일한 문자가 추가로 존재하는 것이므로 전보다 +1을 시켜줘야한다.
대각선에서부터 추가를 하는 이유는 앞선 문자에서 동일한 문자가 있었다면 그 결과에 1을 더해주기 위해서다.

결국 LCS의 길이는 이중 배열의 가장 마지막 인덱스에 저장되므로
위 그림에서는 d[7][6]에 LCS의 길이가 저장된다.

아래 배열은 위 배열과는 다른 종류의 배열로
배열의 각 인덱스의 값이 어떤 위치에서부터 이동되어 왔는지 나타낸다.

 

1과 같은 경우 X.getChar(i) == Y.getChar(j)인 경우,
2는 X.getChar(i) != Y.getChar(j)면서 d[i-1][j]<d[i][j-1]인 경우,
3은 X.getChar(i) != Y.getChar(j)면서 d[i-1][j]>d[i][j-1]인 경우를 나타낸다.

이와 같은 성질을 이용하여,
배열의 맨 마지막 인덱스 위치로부터 
d의 행 또는 열의 인덱스가 0이 될 때까지 이동 경로를 되돌아갔을 때,
그 경로에서 1이 나오는 인덱스의 문자열 내 문자를 역순으로 이어붙이면
LCS를 도출해낼 수 있다.

(1은 X.getChar(i) == Y.getChar(j)인 경우 삽입된 수이기 때문이다.)

 

제출코드

import java.io.*;

public class Main {
    static int c[][];
    static int b[][];
    static String str;
    static String str2;
    static String result="";
    static void getLCS(int x, int y){
        if(x!=0 && y!=0){
            if(b[x][y]==1){
                result=str.charAt(x-1)+result;
                getLCS(x-1,y-1);
            }
            else if(b[x][y]==2) getLCS(x-1,y);
            else getLCS(x,y-1);
        }
    }
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine();
        str2 = br.readLine();

        int strLen=str.length()+1;
        int str2Len=str2.length()+1;

        c = new int[strLen][str2Len];
        b = new int[strLen][str2Len];

        for(int i=1;i<strLen;++i){
            for(int j=1;j<str2Len;++j){
                if(str.charAt(i-1)==str2.charAt(j-1)){
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;
                }
                else{
                    if(c[i-1][j]>c[i][j-1]){
                        c[i][j]=c[i-1][j];
                        b[i][j]=2;
                    }
                    else{
                        c[i][j]=c[i][j-1];
                        b[i][j]=3;
                    }
                }
            }
        }

        getLCS(strLen-1,str2Len-1);

        bw.write(c[strLen-1][str2Len-1]+"\n");
        bw.write(result+"\n");
        bw.flush();
        bw.close();
    }
}