[BOJ] 백준 9252번 LCS2 (Java)

#9252 LCS2

난이도 : 골드 5

유형 : DP

9252번: LCS 2

▸ 문제

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

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

▸ 입력

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

▸ 출력

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

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

 

 

문제 풀이 

LCS 문제의 연장선상의 문제이다. 

 

먼저 LCS를 찾아내기 위해 만들었던 dp 이차원 배열을 보면 쉽게 풀어낼 수 있다.

 

i   \   j	0	C 1	A 2	P 3	C 4	A 5	K 6
0	0	0	0	0	0	0	0
A 1	0	0	1	1	1	1	1
C 2	0	1	1	1	2	2	2
A 3	0	1	2	2	2	3	3
Y 4	0	1	2	2	2	3	3
K 5	0	1	2	2	2	3	4
P 6	0	1	2	3	3	3	4

 

위의 색칠된 숫자를 자세히보면 dp값이 변하는 부분임을 알 수 있다. 그 부분이 LCS를 찾아내는 부분이므로 저 위치들만 골라서 탐색을 해주면 된다.

 

탐색 방식

0,0에서 시작해도 되지만 끝부분인 6,6에서 먼저 타고 내려가는 방법을 택했다.

 

dp값이 줄어드는 절벽 구간에 도달했다면 해당 부분에 속하는 문자를 저장한다. n → 0 하향식으로 값을 저장해주므로 후입선출을 해주는 Stack자료구조를 사용하여 데이터를 저장한다.

1. dp[i][j] == dp[i-1][j] 이면
   1. i → i-1 , j → j 로 이동
2. dp[i][j] == dp[i][j-1] 이면
   1. i → i , j → j-1 로 이동
3. 1,2에 해당하지않으면 해당 부분은 절벽 구간으로 LCS의 문자열이므로 stack에 저장한다.
   1. stack.push(str.charAt(i-1)); 
   2. i → i-1, j →j-1로 이동

 

풀이 코드 

// #9252 dp LCS2 
import java.io.*;
import java.util.Stack;

public class Main {

	static int[][] dp;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		LCS2(str1,str2);
		getLCSToString(str1, str1.length(), str2.length());
		
		
		System.out.println(sb.toString());
	}
	
	static void LCS2 (String str1, String str2) {
		int n1 = str1.length();
		int n2 = str2.length();
		
		dp = new int[n1+1][n2+1];
		int max =-1;
		for(int i=1; i<n1+1; i++) {
			for(int j=1; j<n2+1; j++) {
				if(str1.charAt(i-1) == str2.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[n1][n2] + "\n");
	}
	
	static void getLCSToString(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());
		}
	
		
	}
}