[SW Expert Academy] 최장 공통 부분 수열 (D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWBOHEx66kIDFAWr&categoryId=AWBOHEx66kIDFAWr&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=14

SW Expert Academy

 

참고

https://www.youtube.com/watch?v=ukb5aVT64uY

 

import java.util.ArrayList;
import java.util.Scanner;

class Solution {

	public static char A[], B[];
	public static ArrayList<Character> list;
	public static int dp[][];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();

		for (int tc = 1; tc <= t; tc++) {
			A = sc.next().toCharArray();
			B = sc.next().toCharArray();

			dp = new int[A.length + 1][B.length + 1];
			list = new ArrayList<>();

			for (int i = 1; i <= A.length; i++) {
				for (int j = 1; j <= B.length; j++) {
					if (A[i - 1] == B[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]);
					}
				}
			}

			System.out.println("#" + tc + " " + dp[A.length][B.length]);

			getText(A.length, B.length);

			for (int i = list.size()-1; i >=0; i--) {
				System.out.print(list.get(i));
			}

		}

	}

	public static void getText(int r, int c) {
		if (r == 0 || c == 0) {
			//System.out.println("A[r]:"+(r)+""+"B[r]:"+(c));
			return;
		}
		if (A[r - 1] == B[c - 1]) {
			//System.out.println("A[r-1]:"+(r-1)+""+"B[r-1]:"+(c-1));
			list.add(A[r - 1]);
			getText(r - 1, c - 1);
		} else {
			if (dp[r - 1][c] > dp[r][c-1]) {
				getText(r - 1, c);
			} else {
				getText(r, c - 1);
			}
		}
	}
}

 

길이뿐 아니라 문자를 출력해주는 방법도 공부했다.