BOJ_9252_LCS 2 (Java)

[Gold IV] LCS 2 - 9252

문제 링크

성능 요약

메모리: 23060 KB, 시간: 140 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 9월 8일 23:49:15

문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

코드

/**
 * Author : nowalex322, Kim Hyeonjae
 */

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static long[][] dp;
	static char[] str1, str2;
	static ArrayList<Character> LCS;
	static int N, M, inDegree[];
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		
		str1 = br.readLine().toCharArray();
		str2 = br.readLine().toCharArray();
		
		
		dp = new long[str1.length+1][str2.length+1];
		LCS = new  ArrayList<Character>();
		for(int i=1; i<str1.length+1; i++) {
			for(int j=1; j<str2.length+1; j++) {
				if(str1[i-1] == str2[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]);
				
			}
		}
		getLCS(str1.length, str2.length);
		
		bw.write((int) dp[str1.length][str2.length] + "\n");
		makeLCS();
		bw.flush();
		bw.close();
		br.close();
		
	}
	
	private static void makeLCS() throws IOException {
		for(int i=LCS.size()-1; i>=0; i--) {
			bw.write(LCS.get(i));
		}
	}

	/**
	 * LCS 문자열구하기
	 */
	private static void getLCS(int i, int j) {
		if(i==0 || j==0) return;
		if(str1[i-1]==str2[j-1]) {
			LCS.add(str1[i-1]);
			getLCS(i-1, j-1);
		}
		else {
			if(dp[i-1][j] > dp[i][j-1]) getLCS(i-1, j);
			else getLCS(i, j-1);
		}
	}
	
	
}