[BOJ] 백준 [9252] LCS 2 JAVA

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

9252번: LCS 2

문제

풀이

두 문자열(arr1,arr2) 을 문자 하나하나 비교하는것에서 시작을 해야한다.

( arr1 를 i 로 순차탐색 ) ( arr2 를 j 로 순차탐색)

차례대로 (i, j)비교하다가 만약 문자 하나가 같은경우 => arr1[i] == arr2[j] 일 경우 카운트를 증가시킨다.

이것을 끝날때 까지 진행하면 된다.

 

하지만 이대로하면 중복되는부분이 있는데다가 , 특정 공통문자가 앞에있을때 뒤에있을때 등 모두 따져봐야하므로

3중포문 => O(n^3) 이 되므로 당연히 시간초과 발생.

 

그럼 다시 탐색하지않게 하기위해 기존의 결과를 메모이제이션으로 기록해뒀다가 써야하므로 DP로 접근.

(i,j) 위치에서 두 문자열의 공통되는 부분수열의 길이를 n이라고 하면

DP(i,j) = n 으로 나타낼수 있다.

 

1. (i,j)에서 같은 문자가 발견될경우 , i , j 한칸 전진한 값에 +1 => DP(i+1,j+1) = DP(i,j)+1

2. 같지 않을 경우 , DP(i+1,j+1) 의 값은 DP(i+1,j) or DP(i,j+1) 중 큰 값이랑 동일하므로

 

최종점화식은 다음과 같다.

for(int i=0;i<arr1.length;i++)
   for(int j=0;j<arr2.length;j++)
      dp[i+1][j+1] = arr1[i]==arr2[j] ? dp[i][j]+1 : Math.max(dp[i+1][j],dp[i][j+1]);

 

즉 , 오른쪽 대각선 아래방향으로 Bottom-Up 방식으로 누적 합을 나타내는 방식으로 값을 다 구하면

제일 오른쪽 밑의 값에서 부터 올라오면서 추적하면 된다.

 

 

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;
 
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=0;i<arr1.length;i++)
            for(int j=0;j<arr2.length;j++)
                dp[i+1][j+1] = arr1[i]==arr2[j]
                        ? dp[i][j]+1 : Math.max(dp[i+1][j],dp[i][j+1]);
 
        StringBuilder answer = new StringBuilder();
        int i = arr1.length;
        int j = arr2.length;
 
        while(i>=1 && j>=1){
            if(dp[i][j] == dp[i-1][j])
                i--;
            else if(dp[i][j] == dp[i][j-1])
                j--;
            else {
                answer.insert(0, arr2[j - 1]);
                i--; j--;
            }
        }
        System.out.println(answer.length());
        System.out.println(answer);
 
    }
 
}