[JAVA] 백준 9251번 문제, LCS (최장 공통 부분 수열)

<문제 링크>

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

9251번: LCS

---

<풀이>

 

최장 공통 부분 수열은 두 문자열에서 가장 긴 공통 부분을 구하는 것이다.

예로 들자면 두 문자열 "ACAYKP"와 "CAPCAK"의 최장 공통 부분 수열은 "ACAK"이다.

이론은 굉장히 간단하다. "ACAYKP"를 기준으로 잡고 한 글자씩 "CAPCAK"와 비교해주면 된다.

최장 공통 부분의 길이를 알아내기 위해서는 [첫번째문자열][두번째문자열]의 이차원 배열이 필요하다.

그 배열을 m[i][j]라고 칭하고 0이 있는 인덱스를 0으로 채우면 다음과 같이 공식을 만들 수 있다.

현재 단어와 비교하려는 단어가 같은 경우 [i-1][j-1] + 1의 값을 현재 인덱스에 넣는 것이다. 즉, 대각선 왼쪽 위에 1을 더한 값이다.

같은 단어가 아닐 경우에 [i][j-1] OR [i-1][j] 중 큰 값을 현재 인덱스에 삽입하면 된다. 즉, 왼쪽 또는 위쪽 인덱스 값 중 큰 값을 그대로 가져오면 된다.

---

<코드>

 

import java.util.Scanner;

public class B9251 {

	public static void main(String[] args) { // LCS ( 최장 공통 부분 수열)
		Scanner sc = new Scanner(System.in);

		String a = sc.next(); // 두 문자열 입력 받기
		String b = sc.next();
		
		int[][] m = new int [a.length()+1][b.length()+1]; // 배열 초기화
		for(int i = 0; i < b.length()+1; i++) { // 0번 인덱스 행과 열은 0으로 초기화
			m[0][i] = 0;
		}
		for(int i = 0; i < m.length; i++) {
			m[i][0] = 0;
		}
		
		for(int i = 1; i < m.length; i++) {
			
			for(int j = 1; j < m[i].length; j++) {
			
				if(a.charAt(i-1) == b.charAt(j-1)) { // 문자가 같을 경우
					m[i][j] = m[i-1][j-1] + 1; // i-1, j-1에 있는 숫자 + 1
				}else {
					m[i][j] = Math.max(m[i-1][j], m[i][j-1]); // 문자가 다르면 둘 중 큰 숫자를 입력
				}
				
			}
		}
		
		System.out.println(m[a.length()][b.length()]);
		
		sc.close();
	}

}