[알고리즘] 백준 5582 공통 부분 문자열 Java

문제 정보

플랫폼 : 백준
분류 : Dynamic Programming (동적 프로그래밍)
난이도 : 골드5
링크 : https://www.acmicpc.net/problem/5582

시간제한 및 메모리 제한 검증

O(nm) 풀이 : 시간제한 ok (n과 m은 각각 문자열의 길이)
자료형 : 최대 30억, long

풀이

문제의 예시 입력으로 설명하겠다.
비교 문자열 1 : ABRACADABRA (아브라카다브라)
비교 문자열 2 : ECADADABRBCRDARA

이런 표를 만든다.
각 칸이 의미하는 바는, 해당 행과 열까지의 문자만을 사용했을 때의 공통 부분 문자열의 갯수이다.

말이 어려우므로, 그림을 통해 설명하도록 한다.
오른쪽 표는 왼쪽의 일부 영역을 나타낸다.
1번 : A 와 E 에서 공통 문자열의 갯수
2번 : AB 와 E에서 공통 문자열의 갯수
3번 : ABR 과 E에서 공통 문자열의 갯수
4번 : A 와 EC에서 공통 문자열의 갯수
5번 : AB 와 EC에서 공통 문자열의 갯수
6번 : ABR 과 EC에서 공통 문자열의 갯수
...
를 나타낸다.
표를 하나씩 채워나가다 보면 왼쪽 표의 파란색 영역에는 두 문자열의 공통 문자열 갯수가 채워질 것이다.
그러나! 표를 다 채우고 파란 영역의 값을 정답으로 사용하기에는 수식도 복잡해 질 수 있으므로 실속만 챙기자.

위 사진을 보면 알겠지만, 공통 문자열의 갯수는 가로, 세로에 동일한 문자가 오는 경우 대각선으로 늘어난다. 위와 같은 이론으로 예시 입력을 채워보자.

위와 같은 표가 채워지고, 정답은 공통 문자열 "ADABR" 로 5개이다.
표를 채워가면서 max값을 갱신해
행과 열이 같은 문자일 경우 좌측 상단 + 1만큼 늘어나는데, 파란부분을 처리하기가 곤란할 수도 있다.
따라서, 두 문자열의 길이가 각각 n, m일 때 int[n][m] 을 만들지 말고 int[n+1][m+1]을 만들어서 해결하도록 하자. 어떤 의미냐면

이렇게 대각선도 처리할 수 있게 말이다!

코드

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String cmp1 = br.readLine();
		String cmp2 = br.readLine();
		int len1 = cmp1.length();
		int len2 = cmp2.length();
		int max = 0;
		int[][] map = new int[len1 + 1][len2 + 1];
		for(int i = 1; i <= len1; i++) {
			for(int j = 1; j <= len2; j++) {
				if(cmp1.charAt(i-1) == cmp2.charAt(j-1)) {
					map[i][j] = map[i-1][j-1] + 1;
					max = Math.max(max, map[i][j]);
				}
			}
		}
		System.out.println(max);
	}
}

더 많은 정답 코드

블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.