Backjoon(백준) 9251- LCS (Java)

1. 풀이 힌트 

 - 두 문자열의 문자들을 하나씩 비교하기 위한 격자형의 표를 그린 뒤 왼쪽에 기입한 문자를 기준으로 한 문자씩 위쪽의 문자열들과 비교하여 공통값을 찾아가면 된다. 

 

2. 풀이 과정

 1) 위 사진과 같이 문자열 ABCBDAB와 BDCABA를 비교한다고 가정했을 때, 열에는 ABCBDAB, 행에는 BDCABA를기입한 행렬을 만든다. (직접 공책에 그려가면서 따라해보면 이해하기 쉽습니다:) !!)

 2) 열에 기입한 ABCBDAB 문자열 중에서 첫 번째 문자 A를 시작으로 행에 기입한 문자열 BDCABA와 하나씩 비교해 나아간다.

 

 비교하여 값을 채우는 방법

 - 비교하며 값을 채우는 방식은 2가지가 있다. 먼저, 같은 문자일 경우에는 값을 + 해준다. 현재 위치에서 대각선 왼쪽 위의 값(행과 열 한칸씩 뒤에 있는 값, 즉 왼쪽 위 대각선)에 더하기 1을 해준다. 

 ex) 위의 사진에서 열의 A문자가 행의 첫번 째 A와 만났을 때의 왼쪽 위 대각선의 값은 0이다. 이 값에 1을 더한 값인 1을 기입한다. dp[i][j] = dp[i - 1][j - 1] + 1

 - 값을 채우는 2번째 방법은, 문자가 같지 않을 경우에는 해당 위치에서 직전 행과 이전 열의 값(왼쪽 값과 위의 값)중 최대값을 기입한다.  

ex) 열의 A문자가 행의 2번 째 B문자와 만났을 때 두 문자는 서로 다르지만 해당 위치에서 왼쪽값과 위의 값중 최대 값은 1이므로 현재 위치에 1을 기입한다. dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j])

 

값을 채우는 방법이 복잡할 수도 있지만, 위의 사진에 적힌 행렬을 보면서 따라가면 규칙을 발견할 수 있다.

 

그렇다면 여기서 위와 같이 행렬을 만드는 과정이 왜 필요한지 궁금해 하는 사람이 있을 수 있다.

쉽게 말해서 위 행렬에서 비교하는 작업은 행이 한칸씩 내려갈 때 마다 ABCBDAB의 부분수열과 BDCABA 전체를 비교하는 행위와 같다.

ex) 첫 번째 행은 전부 0이기 때문에 제외하고, 두 번째 행부터는 A와 BDCABA를 비교하는 작업이다. 세 번째 부터는 AB와 BDCABA를 비교하는 작업이다 네 번째 행은 ABC와 BDCABA를 비교하는 작업이다.

 

위와 같은 방식으로 테이블을 채운 뒤 마지막 행의 마지막열에 있는 모서리값이 최대 공통 수열(LCS)의 값이 된다.

 

3. 코드 구현

import java.util.Scanner;

public class LCS {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine(), b = sc.nextLine();
        int[][] dp = new int[b.length() + 1][a.length() + 1];
        
        for (int i = 1; i <= b.length(); i++) {
            for (int j = 1; j <= a.length(); j++) {
                if (b.charAt(i - 1) != a.charAt(j - 1)) {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        
        System.out.println(dp[b.length()][a.length()]);
        
    }

}