[BOJ 9252] LCS 2 (Java)

9252번: LCS 2

생각한 접근법

DP문제는 정확한 점화식을 두고, 어느 값을 메모리에 저장하는지가 핵심이라 생각했다.

그래서 이번 문제는, 1번 문자열을 두고, 2번 문자열의 문자들을 하나씩 확인하면서 LCS를 기록/갱신해야 겠다고 생각했다. 

따라서 2가지 값을 저장하기로 했다.

• int 배열 lcsLen: 1번 문자열의 i번째 문자를 마지막 문자로 가지는 LCS(이하 Part LPS라 명명)의 최대 길이.
• String 배열 lcs: 위의 LCS최대길이에 대응하는 LCS 문자열.

다르게 말하면, 1번 문자열을 고정한 뒤, 2번 문자열의 문자들이 입력됨에 따라 Part LCS가 달라지는 과정을 알고리즘으로 구현했다고 보면 된다.

 

예제 입력으로 설명해보겠다. 1번 문자열 ACAYPK에 2번 문자열 CAPCAK가 입력된 상황이다.

초기화된 정보는 아래와 같다.

(CAPCAK) 이제 2번 문자열의 1번째 문자 C로 정보를 갱신하면 아래와 같다. 갱신하는 순서는 앞에서부터이다. 이는 앞서 존재하는 LCS의 최대 길이를 찾아가며 정보를 갱신해야 하기 때문이다. 아직 존재하는 Part LCS의 최대 길이가 0이므로, 갱신되는 정보는 1일 수밖에 없다.

 

(CAPCAK) 이번엔 2번째 문자 A로 정보를 갱신하면 아래와 같다. 자세히 설명해보면, 1번 문자열의 1번째 문자 A에 대해 갱신할 때, 앞서 존재하는 Part LCS의 최대 길이가 없으므로, 갱신되는 길이는 1이다. 반면, 1번 문자열의 3번째 문자 A에 대해 갱신할 때는, 앞서 존재하는 Part LCS의 최대 길이가 C에서의 1이므로, 갱신되는 길이는 2이다. 

(CAPCAK) 3번째 문자 P로 정보를 갱신하면 아래와 같다. 1번 문자열의 5번째 문자 P에 대해 갱신할 때, 앞서 존재하는 Part LCS 최대 길이가 A에서 2이므로, 갱신되는 길이는 그보다 1만큼 큰 3이다.

(CAPCAK) 4번째 문자 C로 정보를 갱신하면 아래와 같다. 1번 문자열 2번째 문자 C에 대해 갱신하게 되며, 앞서 존재하는 Part LCS 최대 길이가 1이므로, 갱신되는 길이는 2이다.

 

(CAPCAK) 5번째 문자 A로 정보를 갱신하면 아래와 같다. 1번 문자열의 1번째 문자 A에 대해서는, 동일한 문자이기는 하지만 앞서 존재하는 LCS 최대 길이가 없으므로(=0이므로), 기존의 Part LCS 길이인 1이 새로이 갱신되지 않는다. 반면 1번 문자열의 3번째 문자 A에서는, 동일한 문자이며 앞서 존재하는 LCS 최대 길이가 2이므로, 기존 Part LCS 길이인 2보다 새로운 Part LCS 길이 3이 더 크므로 갱신된다.

 

(CAPCAK) 6번째 문자 K로 정보를 갱신하면 아래와 같다. (설명 생략)

따라서 LCS의 길이는 Part LCS중 최대값인 4이며, String 배열에 저장한 Part LCS를 조회하여 ACAK임을 확인할 수 있다. 

자세한 구현은 아래 코드에서 확인할 수 있다.

시간복잡도

두 문자열의 길이의 곱이므로 O(N^2)이다. N이 1,000 이하이고 시간 제한이 0.4초(약 4천만 연산정도) 이므로 아슬아슬하게 가능하다.

공간복잡도

위에 언급한 DP에 사용하는 메모리 2가지를 고려하면 되는데, 문자열 배열인 lcs의 공간복잡도가 O(N^2)이므로, 대략 계산해보면 2Byte x 1,000 x 1,000 = 2MB정도 된다. 넉넉하다.

막혔던 점

처음에는 lcs[i]에 i번째 문자를 마지막 문자로 가지는 LCS 문자열을 저장하지 않고, i번째 문자 바로 직전의 문자의 인덱스를 저장했다. 하지만 그렇게 하니까 연산 과정에서 정보가 덮어써지는 경우가 발생했고, 그로 인해 마지막에 백트래킹으로 LCS문자열을 찾을 때 엉뚱한 문자열이 나오는 오류가 생겼다. 그래서 넉넉한 메모리를 고려하여, LCS 문자열 전체를 바로 저장하는 것으로 수정하여 문제를 해결했다.

배운 점

처음 시도했던 때에는 여러 변수를 가지고 복잡하게 풀려고 했었다. 하지만 풀리지 않아 잠시 냅뒀다.

약 3주 뒤에 DP문제를 이것저것 풀다가 생각나서 다시 도전해봤는데, 의외로 쉽게 풀렸다.

 

이번 문제에서는, N=1,000과 시간제한 0.4초를 보고 O(N^2)의 시간복잡도를 떠올렸고, 그로 인해 두 문자열을 하나씩 조회하는 방식이 적절하겠다는 생각을 했다.

다양한 DP문제를 풀며, 어떻게 해야 적절한 점화식을 얻어낼 수 있는지 요령이 늘은듯 하다.

작성한 코드

import java.io.*;
import java.util.*;

public class Main {

    // 조건
    static char[] str1, str2;

    // DP
    static int[] lcsLen;           // str1에서 현재 위치까지의 LCS길이 기록
    static String[] lcs;     // str1에서 현재 위치까지의 lcs기록

    public static void main (String[] arg0) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력: 문자열 2개
        str1 = br.readLine().toCharArray();
        str2 = br.readLine().toCharArray();
        br.close();

        // dp 초기화
        lcsLen = new int[str1.length];
        lcs = new String[str1.length];

        // str1을 두고, str2의 문자를 순서대로 조회하면 DP 갱신.
        // O(N^2)의 복잡도.
        for (int j=0; j<str2.length; j++) {
            int tempLcsLen = 0;
            String tempLcs = "";
            for (int i=0; i<str1.length; i++) {
                // 문자가 동일하고 새로운 lcs 길이가 더 길면 lcs기록.
                if (str1[i] == str2[j] && lcsLen[i] < tempLcsLen + 1) {
                    lcsLen[i] = tempLcsLen + 1;
                    lcs[i] = tempLcs + str1[i];
                }
                // 문자가 동일하지 않다면 temp 갱신
                else {
                    if (lcsLen[i] > tempLcsLen) {
                        tempLcsLen = lcsLen[i];
                        tempLcs = lcs[i];
                    }
                }
            }
        }

        // dp에서 LCS 최대값 찾기
        int maxLcs = 0;
        int maxIdx = -1;
        for (int i=0; i<str1.length; i++) {
            if (lcsLen[i] > maxLcs) {
                maxLcs = lcsLen[i];
                maxIdx = i;
            }
        }

        // 출력하기
        System.out.println(maxLcs);
        if (maxLcs > 0) {
            System.out.println(lcs[maxIdx]);
        }
    }
}