[java백준] 골드 5/ 9251번 LCS

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

9251번: LCS

import java.io.*;
import java.util.*;
 
import static java.lang.Math.max;
 
public class Main {
    public static int lcs[][];
    public static String []arr1;
    public static String []arr2;
    public static void main(String[]args) throws IOException {
        Scanner sc=new Scanner(System.in);
 
        String []arr1=sc.next().split("");
        String[]arr2=sc.next().split("");
        //두 문자열의 크기가 다를 수 있다!
 
        lcs=new int[arr1.length+1][arr2.length+1];
        for(int i=0;i<=arr1.length;i++){
            lcs[i][0]=0;
        }
        for(int i=0;i<=arr2.length;i++){
            lcs[0][i]=0;
        }
        for(int i=1;i<= arr1.length;i++){
            for(int j=1;j<=arr2.length;j++){
 
                if(arr1[i-1].equals(arr2[j-1])){
                    lcs[i][j]=lcs[i-1][j-1]+1;
                }else{
                    lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
                }
            }
        }
 
       System.out.println(lcs[arr1.length][arr2.length]);
    }
}

 

런타임에러가 자꾸 났는데 이유는 두 문자열의 크기가 다를 수 있기 때문이다. 그래서 첫번째 문자열의 크기를 행의 길이, 두번째 문자열의 크기를 열의 길이로 두고 따로따로 설정해주는 것이 가장 좋다! 

 

LCS알고리즘을 이용하면 된다.

 

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

이 글에서 LCS를 엄청 잘 설명해주셨다. 나도 이걸 보고 이해를 했다.

 

ACAYKP 와 CAPCAK의 최장공통부분 수열을 찾으면 되는데

 

 

우선 A를 기준으로 살펴보자

 

A와 C -> 공통부분이 0이다.

 

A와 CA -> 공통부분이 1

 

A와 CAP ->1

 

A와 CAPC ->1

 

A와 CAPCA ->1

 

A와 CAPCAKS ->1

 

이번에는 C를 기준으로 볼건데, 수열이기 때문에 AC가 된다.

이게 무슨 말이냐면

 

AC와 C 비교 ->공통부분 C로 1

 

AC와 CA -> 공통부분 1 (A또는 C)

 

AC와 CAP ->1

 

AC와 CAPC -> 2(AC)

 

AC와 CAPCA -> 2 (AC)

 

AC와 CAPCAK -> 2

 

 

3번째 인덱스인 A가 기준이 됐을 때도 마찬가지이다. 이번에는 수열이 ACA가 되는데

 

ACA 와 C ->1

ACA와 CA ->2

ACA와 CAP ->2

ACA와 CAPC ->2 (AC)

ACA와 CAPCA ->3(ACA)

ACA와 CAPCAK ->3(ACA)

 

 

마지막 인덱스인 P가 기준일때를 한번 더 보자

 

ACAYKP 와 C -> 1(C)

ACAYKP 와 CA ->2(CA)

ACAYKP와 CAP ->3(CAP)

ACAYKP와 CAPC ->3(CAP)

ACAYKP와 CAPCA -> 3(CAP또는 ACA)

ACAYKP와 CAPCAK ->4 (ACAK)

결론적으로 두 문자가 같으면 LCS[i][j]에 LCS[i-1][j-1]+1을 넣어주면 되고

두 문자가 다르면 이전 행(LCS[i-1][j]) 과 이전 열(LCS[i][j-1]) 중 더 큰 값을 LCS[i][j]에 넣어주면 된다!

 

 

이걸 좀 더 설명하자면

예를 들어 ACA와 CAP 문자열을 비교하는데

    A   C   A

C  

A

P

 

2행 3열은 ACA와 CA를 비교한 것이기에 공통 수열이 2이고

3행 2열은 CAP와 AC를 비교한 것이기에 공통 수열이 1이다.

 

두 문자열 모두 3번째 인덱스인 A와 P가 서로 다르기에 lcs[i-1][j-1]+1을  하는 것이 아닌

2행 3열과  3행 2열 중 더 큰 수열 값이 3행  3열로 들어오게 된다. 그래야 3행 3열에 최장 수열을 넣을 수 있기 때문이다. 둘 중 최장 수열은 2가 된다!

 

또 다른 예로는 3행 3열의 값이 같은 ACA BAA를 봐보자.

 

   A  C  A

B

A

A

 

2행 2열은 AC와 BA의 비교이기 때문에 최장공통 수열은 1이 된다. 여기서 둘 다 똑같이 A가 뒤에 오기 때문에 최장공통수열인 1에 1을 더한 2가 된다. 이걸 일반화 하면 LCS[i][j]=LCS[i-1][j-1]+1이 나온다! 

도움을 받은 글 

 

 

https://st-lab.tistory.com/139

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