[SWEA] - 3304. 최장 공통 부분 수열 (D3)

[문제]

주어진 두 문자열의 최대 공통 부분 수열(Longest Common Sequence)의 길이를 계산하는 프로그램을 작성하시오.
예를 들어 "acaykp"와 "capcak"의 경우, 두 문자열의 최대 공통 부분 수열은 "acak"로 길이가 4이다.
최장 공통 부분문자열(Longest Common Substring)을 계산하는 것이 아님에 주의한다.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에 두 문자열이 공백을 사이에 두고 주어진다.
각 문자열은 알파벳 소문자로만 구성되어 있음이 보장된다.
각 문자열의 길이는 1,000 이하의 자연수이다.

[출력]
각 테스트 케이스마다 ‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 공통 부분 수열의 길이를 출력한다.

문제 풀기

3304. 최장 공통 부분 수열

 

---

[풀이]

• LCS(Longest Common Subsequence)
  1. 문자열 A, B의 한글자씩 비교
  2. 두 문자가 다르다면 LCS[i-1][j]와 LCS[i][j-1] 중에 큰 값을 표시
  3. 두 문자가 같다면 LCS[i-1][j-1] 값을 찾아 +1
  4. 위 과정 반복

import java.util.Scanner;

class Solution {	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			char x[] = sc.next().toCharArray();
			char y[] = sc.next().toCharArray();
			
			int arr[][] = new int[x.length+1][y.length+1];
			
			for(int i=0; i<=x.length; i++) {
				for(int j=0; j<=y.length; j++) {
					if(i == 0 || j == 0) {
						arr[i][j] = 0;
						continue;
					}
					if(x[i-1] == y[j-1]) {
						arr[i][j] = arr[i-1][j-1] + 1;
						continue;
					}
					arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
				}
			}
			System.out.format("#%d %d\n", tc, arr[x.length][y.length]);
		}
	}
}