[BaekJoon] 5582 공통 부분 문자열 (Java)

1.  문제 링크

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

2.  문제

요약

• 어떤 문자열 s의 부분 문자열 t란 s에 t가 연속으로 나타나는 것을 말합니다.
• 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 문제입니다.
• 입력: 첫 번째 줄과 두 번째 줄에 대문자로 구성되어 있으며 길이가 1 이상 4000 이하인 문자열이 주어집니다.
• 출력: 첫 번째 줄에 두 문자열에 모두 포함된 부분 문자열 중 가장 긴 것의 길이를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getLCS(String str1, String str2) {
		int[][] dp = new int[str1.length() + 1][str2.length() + 1];
		int max = 0;
		for(int i = 1; i < dp.length; i++) {
			for(int j = 1; j < dp[i].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]);
				}
			}
		}
		return max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String str1 = br.readLine();
		String str2 = br.readLine();
		br.close();
		Main m = new Main();
		bw.write(m.getLCS(str1, str2) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용한 LCS(Longest Common Substring) 알고리즘을 이용하여 구할 수 있는 문제입니다.
• 두 문자열의 각각의 길이에 맞게 2차원 배열 dp를 생성합니다.
• 배열 dp는 만약 행이 문자열 str1, 열이 문자열 str2를 의미하고 현재 위치가 dp[i, j]라면
  • str1의 i번째 문자와 str2의 j번째 문자에서 부분 문자열의 길이를 의미합니다.
  • 즉, str1의 첫 번째 문자부터 i번째 문자까지의 문자열과 str2의 첫 번째 문자부터 j번째 문자까지의 문자열을 이용하여 dp[i, j] 값을 구합니다.
• 이 때, dp[i, j]의 값은 현재 str1의 i번째 문자와 str2의 j번째 문자가 다르다면 부분 문자열을 이룰 수 없으므로 0이 됩니다.
• 만약 str1의 i번째 문자와 str2의 j번째 문자가 같다면 str1의 (i - 1)번째까지의 문자열과 str2의 (j - 1)번째까지의 문자열을 이용하여 구한 dp[i - 1][j - 1]의 값에 1을 더한 값이 dp[i][j]의 값이 됩니다.
  • dp[i - 1][j - 1]이 현재 비교하고 있는 두 문자 바로 이전에 비교한 두 문자에 대한 부분 문자열의 길이값이기 때문입니다.
• 이를 이용하여 두 문자열에 모두 포함된 부분 문자열 중 가장 긴 것의 길이를 구합니다.

1. 주어진 두 문자열을 각각 변수 str1, 변수 str2에 담고 행의 길이가 (str1의 길이 + 1)이고 열의 길이가 (str2의 길이 + 1)인 2차원 배열 dp를 생성합니다.
2. 두 문자열에 모두 포함된 부분 문자열 중 가장 긴 것의 길이를 나타내는 변수 max를 생성하고 값을 0으로 초기화합니다.
3. 1부터 str1의 길이까지 반복문을 돌며 부분 문자열 중 가장 긴 것의 길이를 구합니다.
   1. 1부터 str2의 길이까지 반복문을 돌며 현재 위치에서의 부분 문자열의 길이를 구합니다.
      1. 만약 각 반복문의 현재 위치에 해당하는 str1의 문자와 str2의 문자가 같다면 위에서 구한 점화식을 이용해 바로 이전에 해당하는 dp[i - 1][j - 1]의 값에 1을 더한 값을 현재 위치에서의 dp값으로 설정합니다.
      2. 현재 max의 값와 현재 dp값 중 더 큰 것을 max로 설정합니다.
4. 3번의 반복문이 끝났을 때의 max의 값이 두 문자열에 모두 포함된 부분 문자열 중 가장 긴 것의 길이이므로 이를 출력합니다.