백준 N9251_LCS(Longest Common Subsequence)

문제

출처 : Baekjoon Online Judge

 LCS는 Longest Common Substring과 Sequence가 있습니다.

이 두 가지의 차이는 LCS가 비교 문자열에서의 연속여부 입니다.

 

 주어진 두 문자열(길이가 다를 수 있음)의 공통된 문자열 중 가장 긴 길이를 탐색하는 문제입니다.

완전탐색으로도 풀이는 가능합니다.

이럴 경우 시간복잡도가 최악의 경우 O(n^n)로 매우 크기 때문에 DP를 이용해야 합니다.

 

 연속되지 않은 문자들을 뽑아도 되지만 순서는 지켜야 하는 조건을 이용하면

문자열 1에 대해 문자열 2를 0번 인덱스부터 점차 비교하는 방식으로 해결이 가능합니다.

풀이

 먼저 DP를 아래 matrix처럼 선언합니다.

여기서 각 0번 index를 0으로 초기화시켜둔 상태로 가정하고 진행하는 이유는

만약 두 문자열 중 하나라도 null값을 가진다면 LCS는 0이기 때문입니다.

 

탐색 전

 

이후 탐색에는 두 가지 조건만 고려하면 됩니다.

 

빨간색 화살표

1. 현재 문자가 비교 문자와 같다면 탐색 중인 두 문자열에 해당 문자를 포함하기 전 상태

즉, 현재 문자의 인덱스가 각각 i와 j일 때 i-1, j-1의 값에 1을 더한다.

점화식 : DP[i][j] = DP[i-1][j-1]+1

 

초록색 화살표

2. 현재 문자가 비교 문자와 다르다면 탐색 중인 두 문자열에 해당 문자를 포함하기 전 상태에서의 최댓값

즉, 현재 문자의 인덱스가 각각 i와 j일 때 i-1, j 값과 i, j-1 값 중 더 큰 값을 그대로 가져온다.

점화식 : DP[i][j] = max(DP[i-1][j], DP[i][j-])

 

탐색 진행 중

반복 수행을 통해 최종 DP mat의 모습입니다.

 

탐색 종료

최종 테이블에서 마지막 row, column의 값이 곧 LCS의 값이 됩니다.

 

코드

public class N9251_LCS {
	public static int[][] DP;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str1 = br.readLine().split("");
		String[] str2 = br.readLine().split("");
		DP = new int[str1.length+1][str2.length+1];
		
		search(str1, str2);
		
		System.out.print(DP[str1.length][str2.length]);
	}
	
	public static void search(String[] str1, String[] str2) {
		for(int i = 0 ; i < str1.length ; i++) {
			for(int j = 0 ; j < str2.length ;j++) {
				if(str1[i].equals(str2[j])) {
					DP[i+1][j+1] = DP[i][j]+1;
				}	else {
					DP[i+1][j+1] = Math.max(DP[i][j+1], DP[i+1][j]);
				}
			}
		}
	}
}