[백준, BOJ 9252] LCS 2 (java)

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

9252번: LCS 2

---

문제

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

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

입력

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

출력

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

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

728x90

 

예제 입력 1

ACAYKP
CAPCAK

예제 출력 1

4
ACAK

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		char[] string1 = br.readLine().toCharArray();
		char[] string2 = br.readLine().toCharArray();
		
		// LCS 길이를 담을 배열
		int[][] arr = new int[string1.length + 1][string2.length + 1];
		for (int i = 1; i <= string1.length; i++) {
			for (int j = 1; j <= string2.length; j++) {
				if(string1[i - 1] == string2[j - 1]) arr[i][j] = arr[i - 1][j - 1] + 1;
				else arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
			}
		}
		
		if(arr[string1.length][string2.length] == 0) sb.append(0); // 부분 문자열의 길이가 0이면 0만 출력
		else {
			int resultSize = arr[string1.length][string2.length]; // 가장 긴 부분 문자열의 길이
			sb.append(resultSize + "\n"); // 문자열 길이 출력에 담자주고
			char[] result = new char[resultSize];// 가장 긴 부분 문자열을 담아줄 배열
			int idx = resultSize - 1; // 현재 배열에 넣을 위치
			int x = string1.length, y = string2.length;
			while(x >= 1 && y >= 1) {
				if(arr[x - 1][y] == arr[x][y]) x--; // 위쪽의 lcs가 같다면 그쪽으로
				else if(arr[x][y - 1] == arr[x][y]) y--; // 왼쪽의 lcs가 같다면 그쪽으로
				else { // 왼쪽 위쪽의 lcs가 모두 작다면
					result[idx--] = string1[x - 1]; // 현재 문자열을 가장 긴 부분 문자열 배열에 담아주고
					x--; // 대각선 위치로
					y--;
				}
			}
			sb.append(String.valueOf(result));
		}
		
		System.out.println(sb);
	}

}