[Algorithm] 백준 DP문제 - 공통 부분 문자열(5582) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 공통 부분 문자열 자바 풀이를 진행하고자 합니다.

문제 출처 https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

 

1. 풀이 소스 

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str1 = br.readLine(); // 입력 받을 문자열
        String str2 = br.readLine(); // 입력 받을 문자열
        int[][] dp = new int[str1.length() + 1][str2.length() + 1]; // 길이 + 1 길이 + 1 로 선언
        
        int max = 0;
        
        // row, col 을 1부터 시작하는 이유는 인덱스 에러 방지 
        for (int row = 1; row <= str1.length(); row++) {
            for (int col = 1; col <= str2.length(); col++) {
                if (str1.charAt(row - 1) == str2.charAt(col - 1)) { // 문자열은 0부터 시작하므로 실제 row = 1에 해당하는 문자는 0 
                    dp[row][col] = dp[row - 1][col - 1] + 1; // 만약 두 문자가 같다면 row - 1, col - 1 인덱스의 dp + 1 (연속된 문자열)
                    max = Math.max(max, dp[row][col]);
                }
            }
        }
        System.out.println(max);
    }
}

 

2. 풀이 중점 사항

 

해당 문제는 연속된 부분 문자열의 가장 큰 크기를 구해야 하는 것이 목표였습니다.

 

str1: ACABACD 

str2: ABABC

 

라는 문자열이 주어졌을 때, 두 문자열의 가장 긴 부분 문자열을 구하는 것은 다음의 표와 같습니다.

 

행의 첫번째 열은 str1의 문자 인덱스 번호이고, 열의 첫 번째 행은 str2의 인덱스 번호입니다.

 

 

(2, 0), (3, 1), (4, 2)의 문자열은 

str1의 ABA,  str2의 ABA입니다. 

이는 곧, 만약 B = B라면, 앞에 row - 1, col - 1의 값에 + 1을 하는 것과 동일하게 됩니다.

왜냐하면, B = B라면 앞에 같은 연속된 문자열이 있을 수도 있는데, 그 값을 DP가 저장하고 있기 때문입니다.

따라서, DP는 현재 주어진 문자열 A의 인덱스와 비교하고자 하는 문자열 B의 인덱스에 있는 문자가 같다면 
이전 연속된 값이 있는지 DP에서 확인하여 +1을 하는 로직을 구할 수 있습니다.

 

dp[row][col] = dp[row - 1][col - 1] + 1; // 만약 두 문자가 같다면 row - 1, col - 1 인덱스의 dp + 1 (연속된 문자열)

따라서, 이와 같은 로직을 구할 수 있게 되는 것 입니다.

 

이상으로 백준 DP 공통 부분 문자열 풀이를 마치도록 하겠습니다.

감사합니다!!!