[BOJ] 백준 9251 LCS (JAVA)

출처 : https://www.acmicpc.net/problem/9251 

9251번: LCS

 

🔍 Solve

완전 탐색으로 문자열 1과 문자열 2를 비교하는 방법을 생각했었는데, 카테고리가 dp인 만큼 시간 초과가 났습니다. 

dp배열에서 i=0, j=0일 때 i-1, j-1을 비교해야하기 때문에 dp배열의 크기는 (문자열 1의 길이+1) * (문자열 2의 길이+1)로 설정하였습니다.

문자열의 문자들을 비교하면서 문자가 같지 않을 땐 dp[i-1][j]와 dp[i][j-1] 중 큰 수를 저장하고, 문자가 같을 땐 dp[i-1][j-1]+1을 저장하였습니다.

그림의 노란색으로 표시된 곳을 해석해보면, {A, C, A} 집합과 {C, A}집합의 LCS가 2라는 것을 의미합니다.

문제를 풀면서 문자열이 같을 때 dp[i-1][j]와 dp[i][j-1] 중 큰 수에 1을 더한 값을 저장하는 실수를 했습니다.

해당 로직은 두 문자열이 ABAAB, AA일 때 반례를 찾을 수 있었습니다.

 

❗ Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static char[] chars1;  //문자열1 char집합
    static char[] chars2;  //문자열2 char집합
    static int[][] dp; 
    static int maxLength = Integer.MIN_VALUE; //LCS의 최댓값

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

        String str1 = br.readLine();
        String str2 = br.readLine();

        chars1 = str1.toCharArray();
        chars2 = str2.toCharArray();

        //dp배열에서 i=0, j=0일 때 i-1, j-1을 탐색하기위해 +1의 크기만큼 배열 선언
        dp = new int[chars1.length+1][chars2.length+1];

        for(int i=1;i<=chars1.length;i++){
            for(int j=1;j<=chars2.length;j++){

                int temp = Math.max(dp[i-1][j], dp[i][j-1]);  //temp = dp배열의 위, 왼쪽 값 중 큰 값 저장
                if(chars1[i-1]==chars2[j-1]){ //만약 두 char가 같으면
                    /*
//                    temp += 1;
                        일 때 안되는 반례
                        str1 = ABAABA
                        str2 = AA
                        temp = Math.max(dp[i-1][j], dp[i][j-1])+1 일 땐 -> 답이 5
                        temp = dp[i-1][j-1]+1일 땐 -> 답이 2
                    */
                    temp = dp[i-1][j-1]+1;  //temp는 dp배열 대각선 위의 값에 +1
                }
                dp[i][j] = temp;  //dp배열에 temp값 저장
                maxLength = Math.max(maxLength, dp[i][j]);  //dp배열 갱신할 때마다 가장 큰 값 저장
            }
        }

        System.out.println(maxLength);

    }
}