[Baekjoon] LCS2 - Java

문제

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

 

풀이

점화식을 도출하고 구하는 것은 이전 포스팅 글을 살펴보면 된다.

[Baekjoon] LCS - Java

 

 

최장 공통 부분 수열을 구하는 방법 중에 제일 쉬운 방법은 문자열도 함께 저장해서 문자를 붙이는 형태로 구현하는 것이다.

근데 메모리 초과가 발생한다. 왜일까?

문자를 저장하는데 1byte라고하자.

1 * 1000(문자열의 길이) * 1000 * 1000 = 약 1GB의 메모리가 필요하다.

하지만, 이 문제에서 메모리 제한은 256MB라고 명시되어 있다.

즉, 다른 방법으로 해결해야한다. 

 

 

배열을 다시 한번 보자.

두 문자열이 "ACAK", "CBAK" 라고 할 때 배열이다.

	C	B	A	K
A	0	0	1	1
C	1	1	1	1
A	1	1	2	2
K	1	1	2	3

 

두 문자열의 최대 깅리를 가지는 부분 문자열은 CAK이다.

 

볼드체로 되어 있는 부분에서 문자를 조합한 것이 최대 길이를 가지는 부분 문자열이 된다.

잘 보면, 왼쪽, 위쪽에서 값이 모두 다를 경우에 대한 문자를 조합한 것이다.

 

그래서 x, y를 우측 하단 값으로 초기화를 하고 값이 위쪽, 왼쪽이 다를 때까지 이동한다. 그리구 그 문자를 저장해서 문자열을 만들면 되는 것이다.

 

소스코드

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

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

        char[] arr1 = br.readLine().toCharArray();
        char[] arr2 = br.readLine().toCharArray();

        int[][] dp = new int[arr1.length + 1][arr2.length + 1];

        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                if (arr1[i - 1] == arr2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        int x = arr1.length;
        int y = arr2.length;

        ArrayDeque<Character> stack = new ArrayDeque<>();

        while (true) {
            if (x == 0 || y == 0) break;

            if (dp[x][y] == dp[x - 1][y]) {
                x -= 1;
            } else if (dp[x][y] == dp[x][y - 1]) {
                y -= 1;
            } else {
                stack.addFirst(arr1[x - 1]);

                x -= 1;
                y -= 1;
            }
        }

        StringBuilder sb = new StringBuilder();

        sb.append(dp[arr1.length][arr2.length]).append("\n");

        while (!stack.isEmpty()) {
            sb.append(stack.removeFirst());
        }

        System.out.print(sb);

        br.close();
    }
}

 

실행결과