BOJ) LCS

LCS

9251번: LCS

풀이

 

이 문제를 통해 LCS 알고리즘을 처음 학습했다.

LCS(Longest Common Subsequence)는 최장 공통 부분 수열을 의미하며, 두 수열이 주어졌을 때, 부분 수열이 되는 수열 중 가장 긴 것을 찾는 것이다.

 

이 문제에서는 알파벳으로 이루어진 두 문장이 주어졌으므로, 두 문자열에서 알파벳의 부분 수열이 공통으로 가장 긴 길이를 찾아야 한다.

 

문제의 예시를 통해 LCS 이론을 살펴보면 다음과 같다.

0	1 ( A )	2 ( C )	3 ( A )	4 ( Y )	5 ( K )	6 ( P )
1 ( C )	0	1	1	1	1	1
2 ( A )	1	1	2	2	2	2
3 ( P )	1	1	2	2	2	3
4 ( C )	1	2	2	2	2	3
5 ( A )	1	2	3	3	3	3
6 ( K )	1	2	3	3	4	4

 

첫번째 문자열의 알파벳을 순회( i )하면서, 두번째 문자열의 알파벳을 순회( j )할 때 같은 경우

= str1.charAt(i-1) == str2.charAt(j -1)     => 1 ~ str1의 길이만큼, 1~ str2의 길이만큼 돌 것. (dp를 str1.len+1, str2.len+1 의 크기로 선언)

=> dp[i][j] = dp[i-1][j-1]+1

 

순회하다가 다른 경우

=> dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1)

 

위와 같은 수식이 나온다.

문제에 적용하면 답을 찾을 수 있다.

 

 

 

코드

 

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

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

        solution(left,right);
    }

    private static void solution(char[] left, char[] right) {
        int answer =0;
        int n = left.length;
        int m = right.length;
        int[][] dp = new int[n+1][m+1];

        for(int i=1; i<=n; i++) {
            int maxLen =0;
            for(int j=1; j<=m; j++) {
                if(left[i-1] == right[j-1]) {
                    dp[i][j] = dp[i-1][j-1]+1;
                    maxLen = dp[i][j];
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
                answer = Math.max(answer,maxLen);
            }
        }

        System.out.println(answer);
    }
}