Baekjoon9251: LCS

LCS

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

40734

16850

12320

40.533%

문제

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

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

입력

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

출력

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

 

풀이

문자열의 부분수열 최대 길이를 풀기 위해 [ 백준-가장 긴 부분 수열 ]의 사고를 연장한다.

이전 문제에서는 i항을 기준으로 탐색하고 있을 때 i항보다 큰 값을 만나면 더 큰 값을 누적하는 방식이었다

이 문제에서는 i항을 기준으로 탐색하고 있을 때 i항의 index보다 작은 값을 만나면 더 큰 값을 누적하도록 한다.

 

간단히 과정을 만들어보면

1항	2항	3항	4항	5항	6항
A	C	A	Y	K	P
C	A	P	C	A	K

C	A	P	C	A	K
0	1	0	0	1	0
0	1	1	1	1	1

1항 A로 아래 문자열을 탐색한다고 한다. A를 아래 텍스트 배열에 적용하면 다음과 같이 변할 것이다. 위는 그 항이 가지고 있는 길이의 최대값이고 아래는 그 값들 중 최대값이다.

C	A	P	C	A	K
1	1	0	2	1	0
0	1	1	2	2	2

2항 탐색부터 규칙이 적용된다. C는 자신과 같은 C를 만나는 순간 왼쪽 탐색을 진행한다. 왼쪽 탐색에서 자신보다 작은 index 중 최대값+1을 가져온다. 3항 A를 한 번 더 시행해보자

C	A	P	C	A	K
1	2	0	2	3	0
0	2	2	2	3	3

A는 2번째와 5번째에 있고 그 때마다 함수가 실행된다.

2번째에서 왼쪽 탐색을 하면 C가 있고 C의 index는 A보다 작다. 2항에 값을 1+1로 바꾼다.

5번째에서 왼쪽 탐색을 하면 A보다 작은 index중 최대값을 가지는 C 2가 있고  2+1로 바꾼다.

 

하지만 아직 문제가 있을 것이다. 현재 i의 항보다 탐색항의 index가 작은지 어떻게 판단할 것인지 정해야한다.

배열에 공간을 하나 더 추가해 값이 갱신될 때마다 최근에 적용한 index값을 기록한다. 그러면 배열 값에는 최대길이와 그 때의 맨 뒤 항의 index가 기록된다.

import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	char[] first = br.readLine().toCharArray();
	char[] second = br.readLine().toCharArray();
	int[] max = new int[second.length]; 
	Integer[] index = new Integer[second.length];
	int out=0; //현존 최대값
	for(int i=0;i<first.length;i++) {
		for(int j=0;j<second.length;j++) {
			if(first[i]==second[j]) { // 같은 문자열을 만났을 때
				if(index[j]==null) { //값이 비어있다면 값을 일단 부여
					index[j]=i;
					max[j]=1;
				}
				for(int k=0;k<j;k++) { //이전 값들을 탐색
					if(index[k]!=null && i>index[k] && max[k]+1>max[j]) {
					//index가 더 작고 max+1보다 큰 값을 가질 때 값을 교체한다
						max[j]=max[k]+1;
						index[j]=i; //교체할 경우 현재 탐색하고 있는 i로 교체
					}
				}
			}
			out=Math.max(out, max[j]);
		}
	}
	System.out.print(out);
}}