[알고리즘] Java / 백준 / LCS 2 / 9252

[알고리즘] Java / 백준 / LCS 2 / 9252

문제

문제 링크

접근 방식

LCS dp 테이블의 점화식은 다음과 같다.

// 만약 문자열1의 i번째 문자와 문자열2의 j번째 문자가 같으면 
// 문자열1의 i-1 번째까지와 문자열2의 j-1번째까지의 공통 부분수열 개수에 1을 더한다.
dp[i][j] = dp[i-1][j-1]+1

// 문자열1의 i번째 문자와 문자열2의 j번째 문자가 다르다면
// 문자열1 i-1번째까지와 문자열2의 j번째까지의 공통 부분수열과
// 문자열1의 i번째까지와 문자열2의 j-1번째까지의 공통 부분수열 개수중 큰 값을 저장한다.
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]);

LCS dp 테이블을 만들었다면 맨 오른쪽 아래 값이 LCS의 길이가 된다.

또한 공통 부분수열을 구하는 방법은 다음과 같다.

1. LCS배열의 가장 오른쪽 아래에서 시작한다. 결과값을 저장할 문자열 answer를 준비한다.
2. dp[i-1][j] 와 dp[i][j-1]중 현재 값과 같은 값을 찾는다
   1. 만약 같은 값이 있다면 해당 값으로 이동한다.
   2. 만약 같은 값이 없다면 answer에 현재 위치의 문자를 넣고 dp[i-1][j-1]로 이동한다.
3. 2번 과정을 반복하다 0으로 이동하면 종료한다. answer를 역순으로 하면 LCS이다.

코드

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

public class Main_9252 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		int [][] dp = new int[str1.length()+1][str2.length()+1];
		
		for(int i=1;i<=str1.length();i++) {
			for(int j=1;j<=str2.length();j++) {
				if(str1.charAt(i-1) == str2.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1] + 1;
				}
				else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		int r = str1.length();
		int c = str2.length();
		
		int len = dp[r][c];
		System.out.println(len);
		
		StringBuilder sb = new StringBuilder();
		
		
		while(true) {
			if(dp[r][c] == dp[r-1][c]) {
				r--;
			}
			else if(dp[r][c] == dp[r][c-1]) {
				c--;
			}
			else {
				sb.append(str1.charAt(r-1));
				r--;
				c--;
			}
			
			if(r <= 0 || c <= 0 || dp[r][c] == 0) break;
		}
		
		System.out.println(sb.reverse().toString());
		
		
		
	}

}