[JAVA] 백준 #5582 공통 부분 문자열 문제 풀이 | Dynamic Programming | 2차원 배열

---

백준 #5582 공통부분 문자열

5582번: 공통 부분 문자열

🔒 문제 설명

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통부분 문자열은 빈 문자열이다.

 

⌨️ 입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

 

🖥️ 출력

첫째 줄에 두 문자열에 모두 포함된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

 

---

🗝️Solution

여러 가지 솔루션들을 찾아보니 대부분이 Dynamic Programming을 사용해서 해결했다. 그중에서 가장 와닿았던 풀이와 해설이 있었고 이를 토대로 이해하고 해결할 수 있었다. 

 

Dynamic Programming
큰 문제를 작은 문제로 분해해 해결하는 알고리즘
하나의 문제는 단 한 번만 풀도록 하는 알고리즘

 

 

이 문제를 통해서 Dynamic Programming의 목적과 정의를 확실히 이해할 수 있었다. 나의 오답 풀이를 보면 중복되는 문제가 많이 반복된다. 여기서 다이나믹 프로그래밍을 활용해서 큰 단위를 작게 분해하고 중복을 막도록 최적화해야 시간 초과를 피할 수 있는 것이다. 

이 문제에서 사용한 Dynamic Programming의 솔루션은 문자열 길이를 담는  2차원 배열을 활용하는 방법이다.

💡풀이 로직

 

해당 솔루션은 컴공맨님의 포스트를 참고해서 작성했습니다.

예제에 나온 ABRACADABRA, ECADADABRBCRDARA 두 문자열을 사용해서 이해해 보자.

 

ABRACA~ 를 S1이라 하고 인덱스는 i, ECADA~ 를 S2라 하고 인덱스는 j라고 하자. 

그리고 두 문자열의 공통 문자열의 길이를 누적해 담는 2차원 배열 Array가 있다.

 

2차원 배열 array는 아래와 같다. 

 

	(공백)	A	B	R	A	C	A	D	A	B	R	A
(공백)	0	0	0	0	0	0	0	0	0	0	0	0
E	0	0	0	0	0	0	0	0	0	0	0	0
C	0	0	0	0	0	1	0	0	0	0	0	0
A	0	1	0	0	1	0	2	0	1	0	0	1
D	0	0	0	0	0	0	0	3	0	0	0	0
A	0	1	0	0	1	0	1	0	4	0	0	1
D	0	0	0	0	0	0	0	2	0	0	0	0
A	0	1	0	0	1	0	1	0	3	0	0	1
B	0	0	2	0	0	0	0	0	0	4	0	0
R	0	0	0	3	0	0	0	0	0	0	5	0
B	0	0	1	0	0	0	0	0	0	1	0	0
C	0	0	0	0	0	1	0	0	0	0	0	0
R	0	0	0	1	0	0	0	0	0	0	1	0
D	0	0	0	0	0	0	0	1	0	0	0	0
A	0	1	0	0	1	0	1	0	2	0	0	1
R	0	0	0	1	0	0	0	0	0	0	1	0
A	0	1	0	0	2	0	1	0	1	0	0	2

 

 

이때, S1[i] == S2[j] 즉, 공통된 글자를 발견했다면 이전까지 연속되는 부분 문자열에 새로 공통된 문자를 추가한다고 생각하는 것이다. S1과 S2에 공통되는 이전 문자인 memo[i -1][j - 1]에 저장된 길이에 + 1을 하여 즉, memo[i -1][j - 1] + 1을 현재 위치에서 공통되는 연속된 부분 문자인 memo[i][j] 갱신하면 된다.

 

	for( int i = 0; i < a.length(); i++ ){
            for(int j = 0; j < b.length(); j++){
                //[2] 서로 같은 문자 찾으면 배열에서 해당 값을 대각선 누적시킨다.
                if(a.charAt(i)==b.charAt(j)){
                    array[i+1][j+1] = array[i][j] + 1;
                    if(max<array[i+1][j+1]) max = array[i+1][j+1];
                }
            }
        }

 

그래서 위의 표와 같이 두 문자열의 최대 공통 문자열 "ADABR"이 될 때 최대 문자열 길이를 누적해 나간 결과인 '5'가 최댓값으로 출력되는 것이다. 

 

Q. 이전까지 연속되는 부분 문자열을 누적한다고? 그런데 내가 지금 찾은 것이 처음 찾은 부분 문자열이라면?  

A. 그렇다면 memo[i -1][j - 1]에 저장된 길이는 0이므로 현재 위치에 저장되는 값은 1일 테니 상관없다. 

 

Q. array [0][0]의 두 문자열이 각각 '공백'으로 된 이유?

A. 이전 결과에 대해 누적해 가는 알고리즘이므로 각 문자열의 첫 글자가 공통일 경우에 대비해 만들어둔 안전장치

 

🗝️해결 코드

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

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

        //[1] 2차원 배열 선언과 동시에 모든 값이 0으로 초기화 된다.
        int[][] array = new int[a.length()+1][b.length()+1];

        int max = 0;
        for( int i = 0; i < a.length(); i++ ){
            for(int j = 0; j < b.length(); j++){
            
                //[2] 서로 같은 문자 찾으면 배열에서 해당 값을 대각선 누적시킨다.
                if(a.charAt(i)==b.charAt(j)){
                    array[i+1][j+1] = array[i][j] + 1;
                    if(max<array[i+1][j+1]) max = array[i+1][j+1];
                }
            }
        }
        System.out.println(max);
    }
}

 

 

참고로 콘솔에서 2차원 배열값을 직접 확인하고 싶으면 이중 for문 바로 뒤에 아래 코드를 붙여서 확인할 수 있다.

        for( int i = 0; i < a.length(); i++ ){
            for(int j = 0; j < b.length(); j++){
                System.out.print(array[i][j]+" ");
            }
            System.out.println();
        }

 

🔗Reference:

-참고한 5582번 정답 코드 : 컴공맨님

[Java] BOJ 5582번 공통 부분 문자열

 

-Dynamic Programming 정의: 피보나치와 함께 설명되어 있는데 이해가 확 와닿는다.

20. 다이나믹 프로그래밍(Dynamic Programming)