[Java] 백준 9252번 LCS 2 - LCS

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

9252번: LCS 2

LCS의 구현 자체는 지난 번에 해서 쉬웠지만

오히려 최장 부분수열 자체를 구하는 데에서 많이 헤맸다.

 

맨 끝부터 탐색해야하는데

처음부터 탐색하고 있으니 당연히 틀릴 수밖에

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

public class g4_9252 {
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);

    public static void main(String[] args) {
        String str1 = fs.next();
        String str2 = fs.next();
        int[][] ans = new int[str2.length() + 1][str1.length() + 1];

        for (int i=1;i<=str2.length();i++){
            char c2 = str2.charAt(i - 1);
            for (int j=1;j<=str1.length();j++){
                char c1 = str1.charAt(j - 1);

                if (c1 == c2){
                    ans[i][j] = ans[i - 1][j - 1] + 1;
                }
                else{
                    ans[i][j] = Math.max(ans[i - 1][j], ans[i][j - 1]);
                }
            }
        }
        
        pw.println(ans[str2.length()][str1.length()]);

        int row = str2.length(), col = str1.length();
        Stack<Character> stack = new Stack<>();
        while (row > 0 && col > 0){
            if (ans[row - 1][col] == ans[row][col]){
                row--;
            }
            else if (ans[row][col - 1] == ans[row][col]){
                col--;
            }
            else{
                stack.add(str1.charAt(col - 1));
                row--;
                col--;
            }
        }

        while (!stack.isEmpty()){
            pw.print(stack.pop());
        }
        
        pw.close();
    }

    // ----------input function----------

    static void sort(int[] a) {
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a)
            L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++)
            a[i] = L.get(i);
    }

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

        String next() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}