[BOJ 백준] 공통 부분 문자열 (5582) Java

링크 : https://www.acmicpc.net/problem/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 이하이다.

 

출력 : 

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

 

예제 입력 : 

ABRACADABRA

ECADADABRBCRDARA

 

예제 출력 : 

5

 

 

접근법 : 

1) 어떻게 풀 것인가?

연속된 공통 부분 문자열을 출력하면 되는 문제이다.

 

2개 String을 각각 i, j 축으로 놓고 

DP[ i ][ j ] 를 첫번째 String의 i번째 char 와 두번째 String의 j번째 char를 비교한다고 했을때 가능한 최대 공통 길이라고 정의하고 풀면 된다.

점화식은 dp[i][j] = dp[i - 1][j - 1] + 1;

 

전체 코드는 아래 참고.

 

2) 시간복잡도

N^2 예상되나, N이 4,000으로 작아 무리 없음

(Java 기준 -  288ms)

 

3) 공간복잡도

N)(4000)이 크지 않아 고려하지 않음

 

4) 풀면서 놓쳤던점

특별히 없음.

 

5) 이 문제를 통해 얻어갈 것

DP 코드 작성법

 

Java 코드 : 

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

public class Main {
	
	static String inputA, inputB;
	static int N, M;		// inputA / inputB 의 길이
	static int [][] dp;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 1. 입력 받기
		inputA = br.readLine();
		inputB = br.readLine();
		N = inputA.length();
		M = inputB.length();
		
		int ans = 0;
		int[][] dp = new int[N + 1][M + 1];
		
		// 2. 대각선 보면서 DP 수행
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (inputA.charAt(i - 1) == inputB.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
					ans = Math.max(ans, dp[i][j]);
				}
			}
		}
		bw.write(String.valueOf(ans));
		
		bw.flush();
		bw.close();
		br.close();
	}
}