백준 9251번 : LCS java

이 문제는 LCS(Longest Common Subsequence) 알고리즘입니다.

이 알고리즘을 위 문제의 예제 입력을 통해 설명드리겠습니다.

주어진 입력들을 받아서 다음과 같이 표로 나타냅니다.

각 셀은 이 구간까지 탐색했을 때 겹치는 subsequence가 얼마나 있느냐입니다.

예를 들어 (2, 3)에 들어가 있는 수는 CA와 ACA가 얼마나 겹치는가입니다.

이 규칙대로 위의 표를 채워보겠습니다.

C 하나와 비교했을 때 2번 column의 C의 subsequence가 되니 그 이후는 전후 1입니다.

CA와 비교할 때 A만 있을 때는 subsequence가 A이지만 ACA와 CA를 비교하면 CA가 겹치니 2가 됩니다.

마찬가지로 CAP가 겹치니 3까지 나옵니다.

CAPC는 위의 문자열과 겹치지 않으므로 변하지 않습니다.

하니만 왼쪽 열의 2번 A와 4번 C는 윗줄의 AC의 subsequence가 되니 이쪽의 셀만 수정해줍니다.

이제 왼쪽 열에서 ACA가 subsequence가 될 수 있으니 이를 수정해줍니다.

마지막 ACAK가 겹칠 때까지 검색하였습니다.

if(firstArr[i-1] == secondArr[j-1])
    lcs[i][j] = lcs[i-1][j-1] + 1;
else
    lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);

이 표를 만드는 방법은 위의 코드와 같습니다.

또한 반대로 이 두 개의 String의 LCS를 찾는 방법은 대각선에서 수가 바뀔 때를 찾으면 됩니다.

다음과 같이 표의 끝에서부터 대각선에서 수가 바뀔 때를 찾아가면 ACAK라는 LCS를 구할 수 있습니다.

이제 소스코드를 보여드리겠습니다.

---

import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String first = br.readLine();
        String second = br.readLine();

        int firstN = first.length();
        int secondN = second.length();

        int[][] lcs = new int[firstN+1][secondN+1];

        char[] firstArr = first.toCharArray();
        char[] secondArr = second.toCharArray();

        for(int i = 1; i<=firstN; i++){
            for(int j = 1; j<=secondN; j++){
                if(firstArr[i-1] == secondArr[j-1])
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                else
                    lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
            }
        }

        System.out.println(lcs[firstN][secondN]);
    }
}