[Algo] 백준 9252 LCS2 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/9252

메모리 : 19172KB

시간 : 172ms

언어 : Java 11

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] arr = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = Math.max(arr[i - 1][j], arr[i][j - 1]);
                }
            }
        }
        Stack<Character> stack = new Stack<>();
        int i = len1;
        int j = len2;
        while (true) {
            if (stack.size() == arr[len1][len2])
                break;
            if (arr[i][j] == arr[i][j - 1]) {
                j--;
            } else if (arr[i][j] == arr[i - 1][j]) {
                i--;
            }
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                stack.add(str1.charAt(i - 1));
                i--;
                j--;
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(arr[str1.length()][str2.length()]).append("\n");
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        System.out.print(sb);
    }
}

풀이

맨 처음에는 LCS알고리즘을 수행하며 String을 저장하는 이차원 배열을 같이 돌리는 코드를 생각했다. 당연히 이게 맞을 줄 알았는데.. 92%에서 시간초과가 나버린.... 어떤 방법을 써도 해결되지않았다ㅜ String+String 연산이 시간초과의 원인인 것 같다. String의 "+" 연산은 금기시 되어 있다는 사실을 알았다... >> 자세한 글 보기

검색을 통해 알아낸 해결방법.. LCS의 길이를 구하기 위한 DP배열을 거꾸로 올라가며 글자를 찾는 것이다. LCS알고리즘에서는 일치하는 부분에서 숫자를 늘려줬다(+1). 따라서 숫자가 늘어난 부분을 찾으면 그 글자가 일치하는 것이라고 볼 수 있다.

     while (true) {
            if (stack.size() == arr[len1][len2]) //모두 찾았으면 break
                break;
            //(i,j)에서 왼쪽과 위를 보며 같은 숫자를 찾아 떠난다.
            //LCS에서 왼쪽과 위 중 큰 것을 저장하며 내려왔기 때문에. 내려온 대로 올라간다!
            if (arr[i][j] == arr[i][j - 1]) {
                j--;
            } else if (arr[i][j] == arr[i - 1][j]) {
                i--;
            }
            //일치하는 문자열을 찾으면 유레카
            //그리고 대각선으로 올라간다. LCS에서 대각선+1 이었기 때문에.
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                stack.add(str1.charAt(i - 1));
                i--;
                j--;
            }
        }