[백준] 9251번: LCS_JAVA

문제 (https://www.acmicpc.net/problem/9251)

 

문제

 

 

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1

4

---

풀이

 

- LCS(Longest Common Subsequence, 최장 공통 부분 수열)란 공통된 가장 긴 부분 수열이다. 즉 임의의 두 수열이 주어졌을 때, 각각의 부분 수열 중 서로 같은 부분 수열 중에서 길이가 가장 긴 부분 수열을 뜻한다. 

 

- 부분 수열은 순서를 가진다. (부분 집합이 아니다)

 

- ACAYKP의 부분 수열은 {A}, {C}, {A}, {Y}, {K}, {P}, {A,C}, ... ,{A,C,A,Y,K,P} 이고

  CAPCAK의 부분 수열은 {C}, {A}, {P}, {C}, {A}, {K}, {C,A}, ... , {C,A,P,C,A,K} 이다.

 

- 서로 같은 부분 수열은 {A}, {C}, {C,A}, ... ,{A,C,A}, ... ,{A,C,A,K}가 있는데 이 중 LCS는 {A,C,A,K}가 된다.

   ACAYKP

   CAPCAK

 

- 아래와 같이 2차원 배열을(표) 이용해서 문제를  해결 해보자. (규칙 찾기)

 

- 아래의 표는 배열이 깊어질수록 문자가 추가되어 부분 수열을 구성하고 표 안에 들어가는 원소(정수 값)는 LCS 길이, 즉 공통 부분 수열의 최대 길이를 뜻한다.

	A: {A}의 부분수열	C: {A,C}의 부분수열	A	Y	K	P: {A,C,A,Y,K,P}의 부분수열
C: {C}의 부분수열
A: {C,A}의 부분수열
P
C
A
K: {C,A,P,C,A,K}의 부분수열

- 글로 설명하는 거보다 예시를 보며 규칙을 찾는 것이 빠르다. 

	A: {A}의 부분수열	C: {A,C}의 부분수열	A	Y	K	P: {A,C,A,Y,K}의 부분수열
C: {C}의 부분수열	0
A: {C,A}의 부분수열	1
P	1
C	1
A	1
K: {C,A,P,C,A}의 부분수열	1

 

- 위 표를 보면 {C,A}의 부분 수열과 {A}의 부분 수열 중 LCS는 {A}이므로 길이는 1이다. 

 

	A: {A}의 부분수열	C: {A,C}의 부분수열	A	Y	K	P: {A,C,A,Y,K}의 부분수열
C: {C}의 부분수열	0	1
A: {C,A}의 부분수열	1	1
P	1	1
C	1	2
A	1	2
K: {C,A,P,C,A}의 부분수열	1	2

- 위 표를 보면 {C,A,P,C} 의 부분 수열 중 {A,C}와 {A,C}의 부분 수열 중 {A,C}가 LCS이므로 길이는 2가 된다.

 

- 이런 식으로 반복하여 표를 완성시키며 규칙을 찾아본다. 

 

	A: {A}의 부분수열	C: {A,C}의 부분수열	A	Y	K	P: {A,C,A,Y,K}의 부분수열
C: {C}의 부분수열	0	1	1	1	1	1
A: {C,A}의 부분수열	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K: {C,A,P,C,A}의 부분수열	1	2	3	3	4	4

- 규칙을 찾았는가?

 

- X번째 원소와 Y번째 원소가 같으면, 해당 칸은 (X-1, Y-1)의 원소 + 1이 된다.

 

- 왜 (X-1, Y-1)의 원소 + 1 이나면, 위 예시에서 1열을 보면 A가 2번째 만나는 경우 이전 행에 + 1할 경우 규칙에 어긋난다. 

 

- X번째 원소와 Y번째 원소가 같지 않으면, 해당 칸은 이전 행의 원소 또는 열 원소 중 큰 것을 채우면 된다. (MAX 함수를 이용하면 되겠쥬?)

 

- 공집합일 경우도 존재하기 때문에, 실제로 코드로 구현할 때는 공집합을 포함해야 한다.

	공집합	A	C	A	Y	K	P
공집합	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

 

- 2차원 배열과 반복문을 이용해서 위 과정을 코드로 구현해보자. 

 

- 위 과정만 떠올릴 수 있다면, 생각보다 간단하다.

 

 

---

코드

public static void main(String[] args) {
 
		Scanner scan = new Scanner(System.in);
		
		char[] str1 = scan.nextLine().toCharArray();
		char[] str2 = scan.nextLine().toCharArray();
		
		//공집합 표현을 위해 인덱스가 한 줄씩 추가, 0으로 초기화 되어 있음.
		int[][] result = new int[str1.length + 1][str2.length + 1];
		
		//1부터 시작, index 0 은 공집합이므로 0으로 초기화 되어 있음.  
		for(int i = 1; i <= str1.length; i++) {
			for(int j = 1; j <= str2.length; j++) {
				
				//(i-1)과 (j-1) 번째 문자가 서로 같은 경우  
				if(str1[i - 1] == str2[j - 1]) {
					//대각선 위 (i-1, j-1)의 result에 +1 한 값으로 대입
					result[i][j] = result[i - 1][j - 1] + 1;	
				}
				
				//같지 않다면 이전 열(i-1)과 이전 행(j-1)의 값 중 큰 값으로 대입
				else {
					result[i][j] = Math.max(result[i - 1][j], result[i][j - 1]);
				}
			}
		}
        
		//마지막 인덱스의 값이 주어진 문자열의 LCS 길이가 된다.
		System.out.println(result[str1.length][str2.length]);
		scan.close();
	}