[백준 알고리즘] 9251번 자바 LCS

문제

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

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

 

입력

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

 

출력

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

 

 

풀이

첫번째 문자열과 비교해서 두번째 문자열의 문자가 들어올때마다 lcs값을 측정해줘야하고
첫번째 문자열의 문자와 새로들어온 문자가 같을때는 해당칸의 lcs와 앞선 문자의 max lcs를 비교해서 수정해줘야한다
그리고 수정한 문자의 위치는 방문체크를 해줘서 이후에 중복으로 안 사용하도록 해야한다

 

그림으로 보면 이해가 쉬울것이다

 

 

이런 과정이 반복되서 최종적으로 K가 들어오면 K는 

y에서 max값이 3이 되기때문에 Math.max(max+1, lcs[j])식을 통해 4라는 값이 저장이 된다.

 

여기서 주의해야할점은 AAA, AAA같은 예시이다. 반복된 경우 지속적으로 값이 커지는 경우가 생기기에  한번돌때 중복되어 증가하는것을 방지해야한다. 따라서 visited를 사용해서 그 경우를 해결했다

 

예제 입력 예시

ACAYKP
CAPCAK

 

예제 출력 예시

4

 

소스코드

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

//9251번 LCS 최장 공통 부분 수열

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] firstCharArr = br.readLine().toCharArray();
        char[] secondCharArr = br.readLine().toCharArray();
        int lcsLen = firstCharArr.length;
        int[] lcs = new int[lcsLen];

        for (int i = 0; i < secondCharArr.length; i++) {
            int max = 0;
            boolean visited[] = new boolean[lcsLen];
            for (int j = 0; j <lcsLen; j++) {
                //앞선 값들중 최대값 찾기
                if(firstCharArr[j] == secondCharArr[i]){
                    if(lcs[j]<max+1){
                        lcs[j] = max+1;
                        visited[j] = true;
                    }
                }
                if(!visited[j]) max = Math.max(max, lcs[j]);
            }
        }

        //LCS최장값 찾기 + 결과값 출력
        int ans = 0;
        for (int i = 0; i < lcsLen; i++) {
            ans = Math.max(ans, lcs[i]);
        }
        System.out.println(ans);
    }
}

 

 

 

 

문제 출처

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

9251번: LCS