🔗 9251번 LCS
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
문제
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
입력
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.
출력
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.
📝 접근 방법 및 풀이
Longest Common Subsequence VS SubString
LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. 우리가 알고 있는 substring과 비교하면 substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다. 문자열 ABCDEFG와 HBCDEGF를 비교해보면,
해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDEG, BCDEF가 될 수 있다. Longest Common Subsequence는 부분수열이기 때문에 문자 사이를 건너뛰면서 공통되는 가장 긴 부분 문자열을 찾으면 된다. 최장 공통 문자열(Longest Common Substring)은 BCDE이다. Longest Common Substring은 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다는 차이가 있다.
접근 방법
str1 = ABCDEG, str2 = HBCDGF로 예시를 구체적으로 들어보자.
맨 앞 문자부터 차례대로 비교해서 부분수열의 길이를 누적해보자. 우선, str1의 첫번째 문자인 A를 기준으로 str2의 문자들을 비교하면 다음과 같다.
str1의 두번째 문자인 B를 기준으로 str2의 문자들을 비교하면 다음과 같다.
{H, B}와 {A, B, C}의 부분 수열은 {B} 이므로 1인 것을 확인할 수 있다. 다음, str1의 세번째 문자인 C를 기준으로 str2의 문자들을 비교하면 다음과 같다.
{H, B, C}와 {A, B, C}의 부분 수열은 {B, C}이므로 2인 것을 확인할 수 있다. 이런 방식으로 채워나가다보면 다음과 같다.
정리하면, 다음과 같은 규칙을 얻을 수 있다.
📌 정리 !
문자열을 비교하여 같았을 때 : 현재 칸에 들어갈 값은 대각선 왼쪽 위의 값(LCS 길이) + 1 이다.
문자열을 비교하여 달랐을 때 : 현재 칸에 들어갈 값은 왼쪽과 위쪽의 값 중 더 큰 값이 들어간다.
이것을 정리하자면 다음과 같다.
x번째 원소와 y번째 원소가 같다면 (x - 1, y - 1)의 LCS 길이 + 1이 된다.
위의 말대로 역추적 루트를 그려보면 다음과 같다.
따라서 str1 = ABCDEG, str2 = HBCDGF의 결과는 BCDG가 되는 것을 알 수 있다.
이런 방식으로 코드를 작성해보자.
💻 코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] str1 = br.readLine().toCharArray();
char[] str2 = br.readLine().toCharArray();
int length_1 = str1.length;
int length_2 = str2.length;
int[][] dp = new int[length_1 + 1][length_2 + 1];
for(int i = 1; i <= length_1; i++) {
for(int j = 1; j <= length_2; j++) {
// (i-1)번째 문자 == (j-1)번째 문자
if(str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
//이전 열(i-1)과 이전 행(j-1)의 값 중 큰 것으로 갱신
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
System.out.println(dp[length_1][length_2]);
}
}