[백준]5582: 공통 부분 문자열 - JAVA
[백준]5582: 공통 부분 문자열
https://www.acmicpc.net/problem/5582
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
풀이
문제 이름에 맞게 "공통 부분 문자열"을 구하는 문제이다. LCS랑 비슷해 보이지만 약간 다르다.
LCS는 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 것이고, 이 문제는 공통 부분 문자열 중에 가장 긴 수열을 찾는 것이다.
두 이론의 차이는 예를 들어 다음과 같다. str1이 ABC이고 str2가 AC일때
LCS를 구하면 2가되며 LCS는 A, C이다.
반면 공통 부분 문자열의 최대 길이는 1이 되며 A 또는 C가된다.
구하려는 값을 이해했다면 이제 문제를 풀어보자.
공통 부분 문자열을 계산할 각각의 문자열을 str1, str2라고 하자.
str1이 ABABA 일때, str1의 부분 수열은 {A} {B} {A, B} {A, B, A} ... {A, B, A, B, A}가 되고,
str2가 AABAB라면 {A} {B} {A, A} {A, B} ... {A, A, B, A, B}가 된다.
str1의 부분수열과 str2의 부분 수열 중에서 공통된 가장 긴 부분 수열을 찾으면 된다.
이를 다이나믹하게 구하는 방법을 알아보자. 우선 아래와 같은 2차원 테이블을 만든다.
가로 행은 str1을, 세로 열은 str2를 의미한다.
| A | B | A | B | A | |
| A | |||||
| A | |||||
| B | |||||
| A | |||||
| B |
이 테이블에 제일 앞 문자부터 비교하며 부분 수열이 공통되는 누적 길이를 배열에 저장해 준다.
str1의 첫 번째 문자(A)를 기준으로 str2문자들과 비교해보자.
| A | B | A | B | A | |
| A | 1 | ||||
| A | 1 | ||||
| B | 1 | ||||
| A | 1 | ||||
| B | 1 |
빨간색으로 색칠된 1의 의미는 str1의 {A}와 str2의 {A} 간의 공통 부분 수열의 길이이다.
주황색으로 색칠된 1의 의미는 str1의 {A}와 str2의 {A, A} 간의 공통 부분 수열의 길이이다.
노란색으로 색칠된 1의 의미는 str1의 {A}와 str2의 {A, A, B} 간의 공톤 부분 수열의 길이이다.
다음으로 str1의 첫 번째 문자와 두 번째 문자로 이루어진 부분 수열을 (A, B) 기준으로 str2문자들과 비교해보자.
| A | B | A | B | A | |
| A | 1 | 1 | |||
| A | 1 | 1 | |||
| B | 1 | 2 | |||
| A | 1 | 2 | |||
| B | 1 | 2 |
빨간색으로 색칠된 1의 의미는 str1의 {A, B}와 str2의 {A} 간의 공통 부분 수열의 길이이다.
노란색으로 색칠된 1의 의미는 str1의 {A, B}와 str2의 {A, A, B} 간의 공통 부분 수얄의 길이이다.
이러한 방법으로 표를 모두 채우면 아래와 같다.
| A | B | A | B | A | |
| A | 1 | 1 | 1 | 1 | 1 |
| A | 1 | 1 | 1 | 1 | 1 |
| B | 1 | 2 | 2 | 2 | 2 |
| A | 1 | 2 | 3 | 3 | 3 |
| B | 1 | 2 | 3 | 4 | 4 |
공통 부분 문자열 길이가 증가하기 시작한 시점을 파란색으로 표시해 보았다.
파란색으로 표시된 부분은 다음과 같은 두 가지 규칙이 존재한다.
- str1과 str2가 같은 문자열일 때 늘어난다.
- 파란색으로 표시된 부분의 좌표가 x, y라고 할 때, x - 1, y - 1값 + 1한 값이 파란색으로 표시된 부분의 값이 된다.
🤔왜 이렇게 되는 것일까?
답은 간단하당. 표의 각각의 좌표는 현재까지의 최대 공통 부분 문자열의 길이를 나타낸다. 이때 서로 같은 문자열이 추가되었다면 전체 길이 또한 +1이 되는 것이다.
이를 코드로 구현해보자.
구현할 때에는 조건절에 str1.charAt(i) == str1.charAt(j)가 아닌, str1.charAt(i - 1) == str1.charAt(j - 1)를 사용해 주고, dp의 크기를 str의 각각 문자열의 길이보다 1크게 설정해 주어 구현하기 간편하게 해준다.
순회 인덱스를 1부터 시작하여 i - 1, j - 1시 아웃오브인덱스 에러가 발생하지 않게 해주고, i - 1, j - 1이 현재 문자열의 위치를 가리킨다. 최대 공통 부분 문자열의 길이는 dp[i][j]에 저장해 주어 사실상 현재 문자열 보다 오른쪽 대각선 한칸 아래에 값을 저장해 준다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str1 = scan.nextLine();
String str2 = scan.nextLine();
int[][] dp = new int[str1.length() + 1][str2.length() + 1];
int max = 0;
for(int i = 1; i <= str1.length(); i++) {
for(int j = 1; j <= str2.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]);
}
}
}
System.out.println(max);
}
}
|
cs |