[백준 알고리즘] 9252번 자바(Java) LCS2

문제

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

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

 

입력

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

출력

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

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

풀이

• 두 문자열중 하나를 기준으로 잡고 다른 하나의 문자열을 반복문 돌리면서 기준으로 잡은 문자열에 최대 길이 LCS를 저장하도록 하는 dp를 생각했다.
• 시간복잡도: O(n*m), 다른 하나의 문자열 m을 문자 하나당 기존 문자열 n만큼 돌려줘야하기 때문이다.
• 기존 LCS문제와 다른점은 이전 index를 역추적해서 해당 LCS의 문자를 완성시켜야한다. 
• 첫 시도 방식(틀림): 따로 배열에 이전에 max값을 가져온 index를 저장하는 방식을 했다. -> 틀린 이유는 추후 반복문에서 max값을 가져온 index의 최대 lcs값이 변경됨에 따라 이전 index의 주소값이 바뀐다는것이다.(아래 그림참고)
• 추후 생각한 방식(성공): 각 index마다 HashMap을 둬서 해당 lcs에 대한 이전의 index값을 구하는 방식을 택했다.

 

원하는 방식이었으나 다음 그림을 보면 첫 시도 방식은 틀린 이유가 나온다. 참고로 아래 그림은 문제 예시와 상관없이 내 코드가 틀린 이유를 설명하는 문자열이다. 문제와 다른 AKPCA기준.

 

위와 같았다면 문자열에는 P가 들어가고 가리키는 index=5에 문자 K를 더하고 이후 index=3문자 A를 더하면

PKA가 되고 reverse 시켜주면 답인 AKP가 나오는것이었다. 문제는 반복문을 다돌리면 아래와 같이 된다.

 

결국 PKAC에 reverse를 적용시키면 답이 CAKP가 되버린다. 따라서 결국 생각한 방법은 해당 index에서 그당시 lcs에 대한 이전 index를 더하자는 생각이었다.

 

그림이 복잡하긴한데 역트래킹 방식은 이제배열[index].get(lcs길이) -> 역index값, 저장은 trackingMap[indeex].add(lcs길이, 역index)로 이해하시면 된다.

 

 

예제 입력 예시

ACAYKP
CAPCAK

 

예제 출력 예시

4
ACAK

 

소스코드

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

// 9252번 LCS2

public class P9252 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] line1 = br.readLine().toCharArray();
        char[] line2 = br.readLine().toCharArray();
        int len1 = line1.length;
        int len2 = line2.length;

        int[] dp = new int[len1];
        HashMap<Integer, Integer>[] trackingMap = new HashMap[len1]; //배열[index].get(lcs길이) -> 역index값, 저장은 trackingMap[indeex].add(lcs길이, 역indx)
        for (int i = 0; i < trackingMap.length; i++) {
            trackingMap[i] = new HashMap<>();
        }

        for(int i = 0; i<len2; i++) {
            int max = 0;
            int index = -1;
            for(int j = 0; j<len1; j++) {
                if(line1[j] == line2[i] && (max+1) >dp[j]) {
                    dp[j] = max+1;
                    trackingMap[j].put(max+1,index);
                }else {
                    if(dp[j] > max) {
                        max = dp[j];
                        index = j;
                    }
                }
            }
        }

        int ans = 0;
        int idx = 0;
        StringBuilder sb = new StringBuilder();
        for (int t = 0; t < len1; t++) {
            if(dp[t]>ans) {
                ans = dp[t];
                idx = t;
            }
        }
        System.out.println(ans);
        //문자열 reverse
        while(idx!= -1&&ans!=0) {
            sb.append(line1[idx]);
            idx = trackingMap[idx].get(ans);
            ans--;
        }
        sb.reverse();
        System.out.println(sb);
    }
}

 

 

 

 

문제 출처

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