[KOITP] LCS

출처 : http://www.koitp.org/problem/LCS/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	424	126 (30%)	111

문제

LCS(최장 공통 부분수열, Longest Common Subsequence)란, 두 수열이 있을 때 두 수열의 공통 부분수열 중 가장 긴 공통 부분수열의 길이를 의미한다.

예를 들어, 수열이 $1,4,2,5$와 $1,2,3,4,5$의 LCS는 $1,2,5$이다.

LCS 문제는 수열이 아닌 문자열에서 주로 다루기도하는데 이 때 문자열의 각 문자가 수열의 수에 해당한다고 보면 된다. 따라서 두 문자열 "ABCBDAB", "BDCABA"의 LCS는 "BCBA"가 된다.

두 문자열이 주어졌을 때, 두 문자열의 LCS를 구하는 프로그램을 작성하시오.

입력

첫 줄에 첫 번째 문자열이 주어지고, 둘째 줄에 두 번째 문자열이 주어진다. 주어지는 문자열은 영어 대문자로만 구성되어 있으며 길이가 1,000을 넘지 않는다.

출력

첫 줄에 주어진 두 문자열의 LCS를 출력한다. 만약 답이 여러 가지인 경우 아무거나 하나 출력한다.

힌트

예제 입력

ABCBDAB
BDCABA

예제 출력

BCBA

< Comment >

 사실 LCS의 길이를 구하는 것 자체는 어려운 문제는 아니었는데, 전체를 출력하려다 보니 한참 헤매었습니다. 어디서 왔는지 저장한 후에, 이를 출력하는 방식을 뒤에서부터 차근차근 올라가며 출력하면 되는 것인데, 왼쪽, 위, 대각선 왼쪽 위 3방향에 대해서 기록을 한 뒤에, 따라가서 그 값을 뒤집어 주면 결과가 됩니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class LCS {
	
	public static char str1Arr[] = null;
	public static char str2Arr[] = null;
	
	public static int dp[][] = null;
	public static int diagonal[][] = null;
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		int len1 = str1.length();
		int len2 = str2.length();
		
		str1Arr = new char[len1 + 1];
		str2Arr = new char[len2 + 1];
		
		for (int i = 1 ; i <= len1 ; i++) {
			str1Arr[i] = str1.charAt(i-1);
		}
		for (int i = 1 ; i <= len2 ; i++) {
			str2Arr[i] = str2.charAt(i-1);
		}
		
		dp = new int[len1 + 1][len2 + 1];
		diagonal =  new int[len1 + 1][len2 + 1];
		for (int i = 1 ; i < len1 + 1 ; i++) {
			
			for (int j = 1 ; j < len2 + 1 ; j++) {
				
				if (str1Arr[i] == str2Arr[j]) {
					dp[i][j] = dp[i-1][j-1] + 1;
					diagonal[i][j] = -1;	// 왼쪽위에서
				} else {
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
					
					if (dp[i][j] == dp[i][j-1]) {
						diagonal[i][j] = 1;		// 왼쪽에서
					} else {
						diagonal[i][j] = 2;		// 위에서
					}
				}
			}
		}
		
		StringBuilder answer = new StringBuilder();
		for (int i = len1, j = len2 ; i > 0 && j > 0 ;) {
				
			if (diagonal[i][j] == -1){
				answer.append(str1Arr[i]);
				i--;
				j--;
			} else {
				
				if (diagonal[i][j] == 1) {		// 위에서
					j--;
				} else {
					i--;
				}
			}
		}

		bw.write(answer.reverse().toString());
		bw.flush();
		bw.close();
	}
}