PS 시나브로

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

문제 요약 : 두 문자열의 가장 긴 부분 수열 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_9252.java

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

public class Main {

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int asz,bsz,i,j,s;
		String stra,strb;
		stra = br.readLine();
		strb = br.readLine();
		asz = stra.length();
		bsz = strb.length();
		int[][] lcs = new int[asz+1][bsz+1];
		for(i=0;i<asz;i++) {
			for(j=0;j<bsz;j++) {
				if(stra.charAt(i)==strb.charAt(j)) {
					lcs[i+1][j+1] = lcs[i][j]+1;
				}else {
					lcs[i+1][j+1] = Math.max(lcs[i][j+1], lcs[i+1][j]);
				}
			}
		}
		s = lcs[asz][bsz];
		sb.append(s+"\n");
        Stack<Character> stack = new Stack<>();
        i = asz;
        j = bsz;
        while(i>0&&j>0) {
        	if(lcs[i-1][j]==lcs[i][j]) {
        		i--;
        		continue;
        	}
        	if(lcs[i][j-1]==lcs[i][j]) {
        		j--;
        		continue;
        	}
        	stack.add(stra.charAt(i-1));
        	i--;
        	j--;
        }
        if(!stack.isEmpty()) {
        	while(!stack.isEmpty()) sb.append(stack.pop());
        	sb.append("\n");
        }
        System.out.println(sb);
	}
}

길이가 a이고 b인 문자열이 있을 때

[a+1][b+1] 크기의 배열을 만들고 다음과 같이 위에서 아래로 왼쪽에서 오른쪽 방향으로 계산해준다.

a의 i번째 문자를 i+1번째 열, b의 j번째 문자를 j+1번째 행이라 할 때

i번째 문자와 j번째 문자가 같을 경우 [i-1][j-1]의 값에서 1을 더해준다.

i번째 문자와 j번째 문자가 다를 경우 [i-1][j] 혹은 [i][j-1]의 값 중 큰 값을 가져온다.

그 결과 오른쪽 아래의 행렬의 값이 두 문자열의 최장 부분 수열 길이가 되며

해당하는 문자열을 구하는 방법은 오른쪽 아래에서 시작하며

왼쪽이나 위쪽값이 해당 값과 같으면 해당 칸으로 이동한다.

왼쪽이나 위쪽값이 해당 값과 다를 경우 대각선으로 한 칸 이동하며 스택에 해당 값에 해당하는 문자열을 추가한다.

최종적으로 스택에 있는 문자열을 출력한다.

예제 ) 

ACAYKP
CAPCAK