Q9252. LCS 2

LCS와 같은 로직에서 String을 출력하는 로직

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Stack; import java.util.StringTokenizer; public class Q9252 { static Stack<Character> result = new Stack<>(); static int[][] dp; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); String firstString = st.nextToken(); st = new StringTokenizer(br.readLine()); String secondString = st.nextToken(); dp = new int[firstString.length()+1][secondString.length()+1]; for (int i = 1; i <= firstString.length(); i++) { int yChar = firstString.charAt(i-1); for (int j = 1; j <= secondString.length(); j++) { int xChar = secondString.charAt(j-1); if (yChar == xChar) { dp[i][j] = dp[i-1][j-1]+1; } else { dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } int maxValue = dp[firstString.length()][secondString.length()]; System.out.println(maxValue); int y = 0, x = 0; for (int i = 1; i <= firstString.length(); i++) { for (int j = 1; j <= secondString.length(); j++) { if (dp[i][j] == maxValue) { y = i; x = j; break; } } if (y != 0) { break; } } for (int j = x; j >= 0; j--) { if (dp[y][j] != maxValue) { if (firstString.charAt(y-1) == secondString.charAt(j)) { result.push(secondString.charAt(j)); maxValue = dp[y][j]; if (maxValue == 0) { break; } } else { j += 1; } y -= 1; } } while(!result.isEmpty()) { System.out.print(result.pop()); } } }