[JAVA] BOJ(백준) - LCS - 9251

문제내용

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

9251번: LCS

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

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

입력

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

출력

 

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

 

---

문제 접근 방법

LCS가 어떤 방식인지 안다면 매우 쉬운 문제이다. 따라서 문제를 풀기위해 LCS가 뭔지 알아봤는데

LCS는 'Longest Common Substring' 과 'Longest Common Subsequence' 로 나뉜다.

 

간략하게 설명하자면

Longest Common Substring 는 연속된 공통된 문자의 부분 수열을 의미한다.

예를들어 BCDABA , CBYPDA 의 경우LCS는 DA가 된다.

 

Longest Common Subsequence 는 문자열이 있을때 연속되지 않아도 공통된 문자의 부분 수열을 의미한다.

단, 순서는 꼭 지켜야한다. 앞으로 문자열을 비교해가며 공통된걸 찾다가 앞이 아닌 뒤에 공통된 문자가 있다고 뒤로 가면 안된다는 말이다.

어쨌든 예를 들면 ACBPYD , CVAKLD 의 경우 LCS는 AD가 된다.

 

위의 의미를 보면 대충 어떤 느낌인지는 온다. 하지만 문제를 풀기위해선 LCS가 어떤 알고리즘을 갖고 있는지 봐야한다.결론부터 말하면 문제에서 LCS는 두가지 경우의수로 나눠서 풀면된다.

 

 

1. 두 문자가 같을때

(arr[i] == arr2[j])  --> LCS(i, j) = LCS(i-1, j-1) +1

2. 두 문자가 다를때

(arr[i] != arr2[j])  --> LCS(i, j) = max( LCS(i-1, j) , LCS(i, j-1) )

 

아래 표를 보면 이해가 조금이라도 쉬울듯하다.

 

dp[i][j]			A	D	C	F	K
		0	1	2	3	4	5
	0	0	0	0	0	0	0
A	1	0	1	1	1	1	1
K	2	0
D	3	0

(1, 1)에서 A는 같은 문자이다. 같은 문자일땐 (i-1 , j-1)+1 을 해줌으로써 dp[1][1] = 1 이 된다.

(1, 2)에서 A와 D는 다른 문자이다. 다른 문자일땐 (i-1, j) 와 (i, j-1) 값중 최댓값을 넣어준다. dp[1][2]=1이 된다.

위의 방식으로 전체 표를 작성하게 되면 아래와같은 결과가 나온다.

 

dp[i][j]			A	D	C	F	K
		0	1	2	3	4	5
	0	0	0	0	0	0	0
A	1	0	1	1	1	1	1
K	2	0	1	1	1	1	2
D	3	0	1	2	2	2	2

그리고 위의 표를 통해 우리가 구하고자 하는 값은 dp[3][5]가 된다.

 

이젠 위의 표와 점화식을 이용해 구현해내기만 하면된다.

 

---

풀이

BottomUp

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

public class Main {
	static int[][] dp; 
	static char[] arr1; //첫번째 문자열을 문자로 나눠 배열에 저장
	static char[] arr2; //두번재 문자열을 문자로 나눠 배열에 저장
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String a = br.readLine();
		String b = br.readLine();
		
		//0행과 0열은 0으로 채워야함. 크기를 하나 늘림.
		//그래야 점화식을 쓸때 인덱스에러가 안남.
		dp = new int[a.length()+1][b.length()+1];
		arr1 = new char[a.length()+1];
		arr2 = new char[b.length()+1];
		
		//dp 초기화 및 arr배열에 문자저장
		for(int i=1; i<=a.length(); i++) {
			arr1[i] = a.charAt(i-1);
			dp[i][0] = 0;
		}
		for(int i=1; i<=b.length(); i++) {
			arr2[i] = b.charAt(i-1);
			dp[0][i] = 0;
		}
		
		//문자하나씩 비교해가며 점화식에 맞게 dp배열을 채워줌.
		for(int i=1; i<=a.length(); i++) {
			for(int j=1; j<=b.length(); j++) {
				if(arr1[i]==arr2[j]) {// 두 문자가 같을때
					dp[i][j] = dp[i-1][j-1]+1;
				}else if(arr1[i]!=arr2[j]) {// 두 문자가 다를때
					dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
				}
			}
		}
		
		//공통문자의 최대길이
		System.out.println(dp[a.length()][b.length()]);
	}
}

 

TopDown

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

public class Main {
	static Integer[][] dp;
	static char[] arr1;
	static char[] arr2;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String a = br.readLine();
		String b = br.readLine();
		
		dp = new Integer[a.length()+1][b.length()+1];
		arr1 = new char[a.length()+1];
		arr2 = new char[b.length()+1];
		
		for(int i=1; i<=a.length(); i++) {
			arr1[i] = a.charAt(i-1);
			dp[i][0] = 0;
		}
		for(int i=1; i<=b.length(); i++) {
			arr2[i] = b.charAt(i-1);
			dp[0][i] = 0;
		}
       	
		dp[0][0]=0; //(0,0)도 초기화 해줘야댐
		
		System.out.println(LCS(a.length(), b.length()));
	}
	
	public static int LCS(int i, int j) {
		if(i==-1 || j==-1) {
			return 0;
		}
		
		if(dp[i][j]==null) {
			if(arr1[i]==arr2[j]) {
				dp[i][j] = LCS(i-1,j-1)+1;
			}else if(arr1[i]!=arr2[j]) {
				dp[i][j] = Math.max(LCS(i-1,j), LCS(i,j-1));
			}
		}
		
		return dp[i][j];
	}
}

 

---

마치며

LCS가 뭔지 알고 어떤식으로 문자를 찾아내는지만 알면 쉽게 풀리는 문제다. 문제를 풀면서 몰랐던 LCS라는 수열을 공부할 수 있는 계기였다.

그리고 풀이에서 나는 문자열을 입력받고 하나씩 문자를 떼가면서 배열에 저장시켰는데

arr = br.readLine().toCharArray(); 을 사용하여 문제를 풀어도 될듯하다.