백준 LCS 2

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

9252번: LCS 2

오랜만에 복습아닌 문제 자바로 풀었습니다. 어려웠던점은 메모리 초과 되는 문제와 시간초과인데 일단 DP로 접근해서 누적값을 문자열을 넣으면 안됩니다.

문자열 입력하면 누적된 이중 메모리가 가득차서 메모리 초과가 발생합니다. 

그래서 숫자를 누적후 숫자의 따라 역추적하여 문자열을 따로 찾아야는 문제입니다. 상당히 어려운 문제입니다.

import java.util.*;

import java.lang.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String x = br.readLine();
        String y = br.readLine();
        int xsize=x.length();
        int ysize=y.length();

        int lists[][]=new int[xsize+1][ysize+1];

        for(int i=0;i<xsize+1;i++) {
            for(int j=0;j<ysize+1;j++) {
                lists[i][j]=0;
            }
        }

        for(int i=0;i<xsize+1;i++) {
            for(int j=0;j<ysize+1;j++) {
                if(i==0||j==0){
                    continue;
                }
                if(x.charAt(i-1)==y.charAt(j-1)){
                   lists[i][j]=lists[i-1][j-1]+1;
                }
                else{
                   lists[i][j]= Math.max( lists[i-1][j], lists[i][j-1] );
                }
            }
        }
        String str="";
        while(xsize!=0&&ysize!=0){
            if(lists[xsize-1][ysize] == lists[xsize][ysize]){
                    xsize-=1;
            }else if(lists[xsize][ysize-1] == lists[xsize][ysize]){
                    ysize-=1;
            }else{
                if(x.charAt( xsize-1 ) == y.charAt( ysize-1 ) ){
                    str+= Character.toString(x.charAt( xsize-1 ));
                }
                xsize-=1;
                ysize-=1;
            }
        }
        System.out.println(str.length());
        String tmp="";
        for(int i=str.length()-1;i>=0;i--){
            tmp+=str.charAt(i);
        }
        if(str.length()>0){
            System.out.println(tmp);
        }
    }
}