[JAVA]백준 9252번: LCS 2

www.acmicpc.net/problem/9252

9252번: LCS 2

 

1. 문제 설명

 

두 문자열의 최장 공통부분 수열의 길이를 출력하고 최장 공통부분 문자열을 출력한다.

 

2. 풀이

 

LCS(최장 공통부분 수열)의 길이를 구하고 역추적하여 최장 공통부분 문자열을 출력하는 문제이다.

 

혹시 LCS의 길이를 구하는 것부터 막힌다면 아래 문제를 먼저 풀어보는 걸 추천한다.

 

www.acmicpc.net/problem/9251

9251번: LCS

 

LCS의 길이를 구하기 위해 입력으로 주어지는 두 문자열의 길이의 크기로 배열 dp [][]를 생성하였다.

 

dp [x][y] : 첫 번째 문자열 x인덱스까지, 두 번째 문자열 y인덱스까지의 최장 공통부분 수열의 길이를 저장

 

 

 

dp [x][y] 배열의 값으로 가능한 경우는 2가지가 있다.

 

 

1. 첫번째 문자열 x 인덱스 문자와 두 번째 문자열 y 인덱스 문자가 같은 경우

 

같을 경우에는 첫 번째 문자열 x-1 인덱스와 두 번째 문자열 y-1 인덱스까지의 최장 공통부분 수열의 길이에서 하나가 더 추가된다.

 

dp [x][y]=dp [x-1][y-1]+1

 

2. 다를 경우

 

다를 경우에는 첫번째 문자열의 x인덱스와 두 번째 문자열의 y인덱스가 LCS에 포함되지 않는다.

따라서 첫 번째 문자열 x-1 인덱스와 두 번째 문자열 y인덱스까지의 최장 공통부분 수열의 길이, 첫 번째 문자열 x 인덱스와 두 번째 문자열 y-1 인덱스까지의 최장 공통부분 수열의 길이 중 더 큰 값을 선택하면 된다.

 

dp [x][y]=Math.max(dp [x-1][y], dp [x][y-1])

 

2가지 경우로 나누어서 dp [][] 배열에 값을 저장한다.

 

그 후 선택한 문자열을 역추적하면 된다.

 

역추적도 dp [][]배열을 사용해서 한다.

 

앞서 dp [][] 배열에 값을 저장할 때 첫 번째 문자열 x 인덱스 문자와 두 번째 문자열 y 인덱스가 다를 경우에는 dp [x-1][y] 값과 dp [x][y-1] 값 중 최댓값을 dp [x][y]에 저장하였고, 같을 경우에는 dp [x-1][y-1] 값에 1을 더하여 저장하였다.

 

따라서 dp [x][y]의 값이 dp[x-1][y], dp [x][y-1] 값과 다를 경우를 찾아가면 된다.

 

dp [x][y]의 값이 dp [x-1][y]와 같다면 왼쪽으로 이동하고, dp [x][y-1]의 값과 같다면 위로 이동하여야 LCS를 추적할 수 있다.

 

둘 다 다르다면 문자가 같은 경우이기에 스택에 추가하고 x-1, y-1 위치로 이동하여 추적을 계속해나가면 된다.

 

 

 

 

 

3. 코드

 

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        String one=br.readLine();
        String two=br.readLine();

        int one_size=one.length();
        int two_size=two.length();

        int[][] dp=new int[one_size+1][two_size+1];

        for(int x=1;x<=one_size;x++){
            for(int y=1;y<=two_size;y++){
                if(one.charAt(x-1)!=two.charAt(y-1))
                    dp[x][y]=Math.max(dp[x-1][y],dp[x][y-1]);
                else
                    dp[x][y]=dp[x-1][y-1]+1;
            }
        }

        int answer=dp[one_size][two_size];

        bw.write(String.valueOf(answer)+"\n");

        Stack<Character> st=new Stack<>();


        int one_index=one_size;
        int two_index=two_size;

        while(dp[one_index][two_index]>0){
            if(dp[one_index][two_index]==dp[one_index-1][two_index])
                one_index--;
            else if(dp[one_index][two_index]==dp[one_index][two_index-1])
                two_index--;
            else{
                st.add(one.charAt(one_index-1));
                one_index--;
                two_index--;
            }
        }


        int size=st.size();

        for(int index=0;index<size;index++){
            bw.write(st.pop());
        }




        bw.flush();
        bw.close();
        br.close();



    }


}