코드트리 [자바 java] 최장 공통 부분 수열

https://www.codetree.ai/missions/2/problems/longest-common-sequence?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 문자열 두 개가 주어지고, 이 두 문자열의 부분 문자열 중 가장 길게 겹치는 문자의 길이를 구해야 한다.

ABA ABBA 테스트케이스로 예를 들어보자면,

 

	A	B	B	A
A	1	1	1	1
B	1
A	1

위 표를 dp라고 보면, 열은 첫번째 문자열, 행은 두번째 문자열을 나타낸다.

dp[i][j]는 첫번째 문자열의 i번째 문자, 두번째 문자열의 j번째 문자까지 비교했을 때의 겹치는 최댓값을 의미한다.

따라서 위 표에서의 dp[1][1]은 A와 A를 비교한 것이므로 1이다. 

우선, 행과 열을 모두 채워주었다. 0부터 문자열의 길이까지 탐색하면서 한번이라도 문자가 겹치면 그 뒤로는 전부 1을 넣어준다. 그 이후에는 아무리 겹쳐도 A와 비교하는 것이기 때문에 1을 넘길 수 없기 때문이다.

 

	A	B	B	A
A	1	1	1	1
B	1	2
A	1	2

 그 다음 나머지 dp를 채운다. dp[2][2]를 보면, 둘 다 B이므로 문자열 증가가 필요하다. 이 때 dp[i-1][j-1]값에 1을 더한 값을 dp[i][j]에 넣으면 된다. 

만약 dp[3][2]와 같이 문자가 일치하지 않으면 왼쪽이나 위의 dp값 중 큰 값을 해당 dp에 넣는다. 

AB와 AB를 비교한 것과 ABA와 A를 비교한 것 모두 해당 dp에서 비교하는 문자열인 ABA와 AB에 포함되기 때문이다. 

 

이러한 방식으로 끝까지 채우고, 최종적으로 모두 비교한 값인 dp[3][4]를 출력하면 된다.

 

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


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

        char[] aa = a.toCharArray();
        char[] bb = b.toCharArray();

        int[][] dp = new int[aa.length][bb.length];

        int ok = 0;//이제까지 aa[0]과 같은 char 존재하지 않음

        for(int i = 0;i<bb.length;i++){ //dp첫 행 채우기
            if(bb[i] == aa[0]) ok = 1;
            if(ok == 0) dp[0][i] = 0;
            else dp[0][i] = 1;
        }

        ok = 0;//이제까지 bb[0]과 같은 char 존재하지 않음

        for(int i = 0;i<aa.length;i++){ //dp 첫 열 채우기
            if(aa[i] == bb[0]) ok = 1;
            if(ok == 0) dp[i][0] = 0;
            else dp[i][0] = 1;
        }

        for(int i = 1;i<aa.length;i++){
            for(int j = 1;j<bb.length;j++){
                if(aa[i] == bb[j]){//현재 탐색하는 두 char값이 일치할 때
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }

        System.out.println(dp[aa.length-1][bb.length-1]);

    }
}

문자가 같지 않은 경우에 대한 처리를 할 때 위에 있는 것은 고려를 하지 않아서 틀렸었다.