139. 9251(LCS)

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] A = br.readLine().split("");
		String[] B = br.readLine().split("");

		int LengthA = A.length + 1;
		int LengthB = B.length + 1;

		int[][] arr = new int[LengthA][LengthB];

		for (int i = 1; i < LengthA; i++) {
			for (int j = 1; j < LengthB; j++) {
				if(A[i-1].equals(B[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]);
				}
			}
		}
		System.out.println(arr[A.length][B.length]);
	}
}

문제요약

첫번째 문자열과 두번째 문자열의 부분 수열이 되는 것 중 가장 긴 것을 찾아라.

설명

일치하는 문자를 구하라는 문제가 아니라 부분 수열이 되는 수열 중 가장 긴 수열을 구하라는 것이다.

2차원 배열을 이용하여 두 문자열의 문자를 비교하면서 가장 긴 수열을 찾아 나간다.

i를 기준으로 j를 탐색하면서 같으면 1 증가, 같지 않으면 i 전 인덱스, j 전 인덱스 중 큰 값을 갖는다.

순차적으로 증가하면서  배열의 마지막 부분이 가장 큰 길이가 된다.

 

		String[] A = br.readLine().split("");
		String[] B = br.readLine().split("");

		int LengthA = A.length + 1;
		int LengthB = B.length + 1;

		int[][] arr = new int[LengthA][LengthB];

초기값 세팅이다.

크게 어렵지 않을 것이다.

 

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

순차적으로 증가시키면서 수열 중 가장 긴 것을 찾는다.