백준 9252 - LCS

문제

---

[참고] : https://soojong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9E%90%EB%B0%94-%EB%B0%B1%EC%A4%80-9252%EB%B2%88-LCS-2

LCS(Longest Common Subsequence)

---

Code

package test;

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

public class P9252 {
	static int[][] dp = new int[1001][1001];
	
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// two sequences
		String seq_1 = br.readLine();
		String seq_2 = br.readLine();
		
		LCS(seq_1, seq_2);
		getSubseq(seq_1, seq_1.length(), seq_2.length());
		
		System.out.println(sb.toString());
		
	}
	
	private static void LCS(String seq_1, String seq_2) {
		int len_1 = seq_1.length();
		int len_2 = seq_2.length();
		
		for(int i = 1; i <= len_1; i++) {
			for(int j = 1; j <= len_2; j++) {
				if(seq_1.charAt(i - 1) == seq_2.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]);
				}
			}
		}
		sb.append(dp[len_1][len_2]).append('\n');		
	}
	private static void getSubseq(String str, int i, int j) {
		Stack<Character> st = new Stack<>();
		while(i > 0 && j > 0) {
			if(i == 0 || j == 0) {
				break;
			} 
			if(dp[i][j] == dp[i - 1][j]) {
				i--;
			} else if(dp[i][j] == dp[i][j - 1]) {
				j--;
			} else {
				st.push(str.charAt(i - 1));
				i--;
				j--;
			}
		}
		while(!st.isEmpty()) {
			sb.append(st.pop());
		}
	}
}