[백준]5582: 공통 부분 문자열 - JAVA

[백준]5582: 공통 부분 문자열

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

5582번: 공통 부분 문자열

풀이

문제 이름에 맞게 "공통 부분 문자열"을 구하는 문제이다. LCS랑 비슷해 보이지만 약간 다르다. 

LCS는 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 것이고, 이 문제는 공통 부분 문자열 중에 가장 긴 수열을 찾는 것이다. 

 

두 이론의 차이는 예를 들어 다음과 같다. str1이 ABC이고 str2가 AC일때

LCS를 구하면 2가되며 LCS는 A, C이다.

반면 공통 부분 문자열의 최대 길이는 1이 되며 A 또는 C가된다.

 

구하려는 값을 이해했다면 이제 문제를 풀어보자.

 

공통 부분 문자열을 계산할 각각의 문자열을 str1, str2라고 하자. 

str1이 ABABA 일때, str1의 부분 수열은 {A} {B} {A, B} {A, B, A} ... {A, B, A, B, A}가 되고,

str2가 AABAB라면 {A} {B} {A, A} {A, B} ... {A, A, B, A, B}가 된다.

 

str1의 부분수열과 str2의 부분 수열 중에서 공통된 가장 긴 부분 수열을 찾으면 된다.

 

이를 다이나믹하게 구하는 방법을 알아보자. 우선 아래와 같은 2차원 테이블을 만든다. 

가로 행은 str1을, 세로 열은 str2를 의미한다.

	A	B	A	B	A
A
A
B
A
B

 

이 테이블에 제일 앞 문자부터 비교하며 부분 수열이 공통되는 누적 길이를 배열에 저장해 준다. 

str1의 첫 번째 문자(A)를 기준으로 str2문자들과 비교해보자.

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

빨간색으로 색칠된 1의 의미는 str1의 {A}와 str2의 {A} 간의 공통 부분 수열의 길이이다.

주황색으로 색칠된 1의 의미는 str1의 {A}와 str2의 {A, A} 간의 공통 부분 수열의 길이이다.

노란색으로 색칠된 1의 의미는 str1의 {A}와 str2의 {A, A, B} 간의 공톤 부분 수열의 길이이다.

 

다음으로 str1의 첫 번째 문자와 두 번째 문자로 이루어진 부분 수열을 (A, B) 기준으로 str2문자들과 비교해보자.

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

빨간색으로 색칠된 1의 의미는 str1의 {A, B}와 str2의 {A} 간의 공통 부분 수열의 길이이다.

노란색으로 색칠된 1의 의미는 str1의 {A, B}와 str2의 {A, A, B} 간의 공통 부분 수얄의 길이이다.

 

이러한 방법으로 표를 모두 채우면 아래와 같다.

	A	B	A	B	A
A	1	1	1	1	1
A	1	1	1	1	1
B	1	2	2	2	2
A	1	2	3	3	3
B	1	2	3	4	4

공통 부분 문자열 길이가 증가하기 시작한 시점을 파란색으로 표시해 보았다.

 

파란색으로 표시된 부분은 다음과 같은 두 가지 규칙이 존재한다.

1. str1과 str2가 같은 문자열일 때 늘어난다.
2. 파란색으로 표시된 부분의 좌표가 x, y라고 할 때, x - 1, y - 1값 + 1한 값이 파란색으로 표시된 부분의 값이 된다.

 

🤔왜 이렇게 되는 것일까?

답은 간단하당. 표의 각각의 좌표는 현재까지의 최대 공통 부분 문자열의 길이를 나타낸다. 이때 서로 같은 문자열이 추가되었다면 전체 길이 또한 +1이 되는 것이다.

 

이를 코드로 구현해보자. 

 

구현할 때에는 조건절에 str1.charAt(i) == str1.charAt(j)가 아닌, str1.charAt(i - 1) == str1.charAt(j - 1)를 사용해 주고, dp의 크기를 str의 각각 문자열의 길이보다 1크게 설정해 주어 구현하기 간편하게 해준다. 

 

순회 인덱스를 1부터 시작하여 i - 1, j - 1시 아웃오브인덱스 에러가 발생하지 않게 해주고, i - 1, j - 1이 현재 문자열의 위치를 가리킨다. 최대 공통 부분 문자열의 길이는 dp[i][j]에 저장해 주어 사실상 현재 문자열 보다 오른쪽 대각선 한칸 아래에 값을 저장해 준다.

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        String str1 = scan.nextLine();
        String str2 = scan.nextLine();
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
 
        int max = 0;
        for(int i = 1; i <= str1.length(); i++) {
            for(int j = 1; j <= str2.length(); j++) {
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        System.out.println(max);
    }
}