9251, 9252 - LCS, LCS 2 : JAVA

https://www.acmicpc.net/problem/9251

9251번: LCS

 

https://www.acmicpc.net/problem/9252

9252번: LCS 2

최장 공통 부분 수열은, 두 수열이 주어졌을때 부분 수열 중 가장 긴 것을 찾는 문제이다.

LCS1은 두 문자열 LCS를 비교하여 길이만 출력하는 알고리즘,

LCS2는두 문자열을 비교한 길이와 LCS를 출력하는 알고리즘을 요구하고,

LCS3은 세 문자열을 비교한 길이를 출력하는 알고리즘을 요구한다.

 

두 문자열간 길이를 비교하여 저장하고 갱신하는 메모라이즈가 필요한 문제로 알려져있고, 

최댓값을 비교하는 과정이 필요하다 생각하여 이차원 dp를 사용해서 값을 구했다. 

 

다만 LCS를 구하는 과정에서 두 부분이 바뀌어도 LCS는 똑같음을 고려하지 않고 처리를 했기에, 오답이 발생하였다.

뒤에서부터 처리하면 비교 문자열의 순서가 바뀌어도 변함이 없음을 알고 그렇게 짰고 결국 맞았다.

오답 코드는 주석처리를 하였다.

import java.util.*;
import java.io.*;
public class sol056 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = new String[2];
		StringBuilder res =new StringBuilder();
		for(int i = 0; i < s.length; i++) {
			s[i] = br.readLine();
		}
		int[][] dp = new int[s[0].length()+1][s[1].length()+1];
		for(int i = 1; i <= s[0].length(); i++) {
			for(int j = 1; j <= s[1].length(); j++) {
				if(s[0].charAt(i-1) == s[1].charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1]+1;
				}
				else {
					dp[i][j] = Math.max(dp[i-1][j], Math.max(dp[i][j-1], dp[i][j]));
				}
			}
		}
		int a = s[0].length();
		int b = s[1].length();
		StringBuilder sb = new StringBuilder();
		while(a > 0 && b > 0) {
			if(s[0].charAt(a-1) == s[1].charAt(b-1)) {
				sb.insert(0, s[0].charAt(a-1));
				if(res.length() == dp[a][b]) {
					System.out.print(sb.toString());
					break;
				}
				a--;
				b--;
			}
			else {
				if(dp[a-1][b] > dp[a][b-1]) {
					a--;
				}
				else {
					b--;
				}
			}
		}
		/*
		int m = 1;
		for(int i = 1; i <= s[0].length(); i++) {
			for(int j = m; j <= s[1].length(); j++) {
				if(s[0].charAt(i-1) == s[1].charAt(j-1)) {
					res.append(s[0].charAt(i-1));
					m = j+1;
					break;
				}
			}
		}
		*/
		System.out.println(dp[s[0].length()][s[1].length()]);
		System.out.println(sb.toString());
	}
}