[JAVA] 백준 9251 LCS

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

9251번: LCS

 

- LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때 , 모두의 부분 수열이 된느 가장 긴 것을 찾는 문제 

 

- 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 

 

- 입력으로 주어진 두 문자열의 LCS의 길이를 출력 

 

 

풀이 과정 

 

Longest Common Subsequence

 

[알고리즘 정리] 최장 공통 부분 수열(LCS) (tistory.com)

[알고리즘 정리] 최장 공통 부분 수열(LCS)

[백준] 9251번 : LCS - JAVA [자바] (tistory.com)

[백준] 9251번 : LCS - JAVA [자바]

 

- 최장 공통 부분 수열

- 어떤 문자열이 두 개 있을 때, 두 수열 사이에 있는 공통적인 문자들의 가장 긴 조합을 찾는 문제 

 

ex)

X= (A, B, C, B, D, A, B)

Y= (B, D, C, A, B, A)

 

- 두 문자열 사이에는 많은 부분 문자열들이 있는데, 문자가 하나 뿐인 부분 문자열을 제외하고 모두 나열하면 다음과 같음 

A,B

A,B,A

B,C

B,C,B

C,B

C,B,A

B,D

B,D,A

B,D,A,B

 

- 이 중에서 가장 긴 부분 문자열은 B,D,A,B가 됨 

 

- 문제를 일반화하기 위해서 비교해야하는 문자열을 X=<x1,x2,..., xm>, Y={y1,y2,...,yn>라 하고, 두 문자열의 LCS를 Z={z1,z2,...,zk>라고 해 보자.

 

- 다음과 같은 명제가 성립한다고 할 수 있다.

 

1) xm = yn이라면, xm=ym=zk이고 새로운 LCS는 Xm-1와 Yn-1이라고 할 수 있다 

 

2) xm != yn이라면, xm !=zk이고 새로운 LCS는 Xm-1와 Y이라고 할 수 있다. 

 

3) xm != yn이라면, yn != zk이고 새로운 LCS는 X와 Yn-1이라고 할 수 있다. 

 

- 만약 두 문자가 다르다고 한다면, 두 가지 경우를 생각할 수 있다. 

- X 문자열의 길이를 줄이거나, Y 문자열의 길이를 줄이는 것이다.

 

- c[i,j]가 i,y 사이의 최대 부분 문자열 길이를 가지고 있다면, X와 Y의 문자가 같을 때, 바로 이전 최장 문자열의 길이에 1을 더한 값을 새로 저장하고, 두 문자가 다를 때는 X쪽 최장 문자열의 길이와 Y쪽 최장 문자열의 길이를 비교해서 더 큰 값을 가져온다. 

 

- 위 계산식 대로 진행하면, 결국 똑같은 연산을 계속해서 해야하는 상황을 맞이한다.

- 따라서 한번 계산한 결과를 테이블에 저장해두고 재사용하는 방식을 시도해야 한다.

 

- 모든 X의 문자에 대해서 Y의 문자를 꺼내와 비교해서 위에서 작성했던 수식에 따라 값을 채워 넣자 

 

- A를 만났을 때는 이전 값 중 제일 큰 0을 넣어주었다. 그리고 B를 만나게 되면 Xi와 Yj의 값이 같기 때문에 이전 위치의 가장 긴 길이인 0에 1을 더해 1로 채워주고 있다.

 

-C를 체크해보면 B와 C는 다른 값이기 때문에, X를 제외했을 떄, 즉 바로 왼쪽에 있는 값과, Y를 제외했을 때, 즉 좌측 대각선 위에 있는 값 중에 더 큰 값으로 배열을 채워주게 된다.

 

-이 논리대로 테이블을 모두 채워나가면 다음과 같이 표를 완성시킬 수 있다. 

 

 

 

- LCS의 길이는 4이고, 해당 길이로 조합할 수 있는 부분 문자열은 총 3종류가 된다. 

- LCS는 여러개가 나올 수 있고 표에서 최대값을 가지는 아이템의 갯수가 그 경우의 수를 의미하기 때문이다.

 

 

정답 

 

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

public class Main {
    static int memo[][] = new int [1001][1001];
    
    public static void main(String[] args)throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        
        char[] s1 = br.readLine().toCharArray();
        char[] s2 = br.readLine().toCharArray();
        
        int len1 = s1.length;
        int len2 = s2.length;
        
        int memo[][] = new int[len1+1][len2+1];
        
        for(int i=1; i<=len1;i++)
        {
        	for(int j=1; j<=len2; j++)
        	{
        		//(i-1)과 (j-1)번쨰 문자가 서로 같다면
        		if(s1[i-1]==s2[j-1])
        		{
        			memo[i][j] = memo[i-1][j-1]+1;
        		}
        		else
        		{
        			//같지 않다면 이전 열(i-1)과 이전 행(j-1)의 값 중 큰 것으로 갱신
        			memo[i][j] = Math.max(memo[i-1][j],memo[i][j-1]);
        		}
        	}
        }
        
        bw.write(memo[len1][len2]+"");
       
        bw.flush();
        bw.close();
        
    }
}