11056번: 두 부분 문자열

문제링크

문제

두 문자열 A와 B가 주어진다. 이 때, A와 B를 부분 문자열로 가지는 문자열 S를 구하는 프로그램을 작성하시오. 가능한 S가 여러가지인 경우 길이가 가장 짧은 것을 출력한다.

예를 들어, A = "baekjoon", B = "hongjun"인 경우 가능한 S중 길이가 가장 짧은 것 중 하나는 "baekhongjouon"이다.

입력

첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

첫째 줄에 A와 B를 부분 문자열로 가지는 가장 짧은 S의 길이를 출력한다.

---

이 문제는 LCS(Longest Common Subsequence) - 최장공통부분문자열 문제이다.

LCS는 연속되지 않은 부분 문자열의 최대 길이를 해결해야 할 때 쓴다.

  DP(Dynamic Programming)으로 특정 범위까지의 값을 구하고 다른 범위까지의 값을 구할때 이전에 구해 둔 값을 이용하여 효율적으로 문제를 해결한다.

 LCS는 2개의 String을 비교하여 최장 공통 부분 문자열을 구해야한다. substring을 구하는 것과 다르게 연속적이지 않아도 되기 때문에 같은 길이의 다른 해가 나타날 수 있다.

예시를 가지고 생각해 보자. 문자열 'ACAYKP'와 'CAPCAK'가 있다고 가정해보자.

우선 하나의 String을 기준 String, 다른 String을 비교 String으로 둔다. 

 위 표를 보면 문자열 맨 앞에 0을 추가해 첫번째 행과 열이 모두 0이다. 두번째 열인 C열의 값을 집어 넣어 보자. 각 위치의 값은 LSC의 길이의 값이 들어간다.

 값을 다 집어 넣으면 위 표와 같이 된다. 표를 읽는 법을 다시 설명하면 [C,C]의 1은 'C'와 'AC' 사이의 LCS의 길이이다. 마찬가지로 [C,Y]의 1은 'C'와 'ACAY'의 LCS의 길이를 나타낸 것이다.

몇 번더 반복해 보자

 위 두표를 보면 알 수 있듯이 가로줄, 즉 행은 이전 행의 값을 기반으로 해서 계산된다. 위의 두 표 중 1번째 표는 'CA'와 'ACAYKP'의 subsequence를 구한것이고, 2번째 표는 'CAP'와 'ACAYKP'의 subsequence를 구한 것이다.

 우리는 여기에서 표의 값을 구할 때 같은 문자가 나오면 이전까지의 LCS의 길이에 +1을 하는 것을 알 수 있다. 여기에서 이전까지의 LCS의 길이란 왼쪽값이 아니라 대각선(왼쪽 위)값을 말한다. 이는 두 문자열에서 해당 두 문자를 비교하기 전의 LCS의 길이에 +1을 하기 위해서 이다.

 또한 비교한 문자가 다르다면, 비교한 문자가 포함되어 있는 직전 LCS, 즉 표에서는 위와 왼쪽 값중 큰 값이 오게된다. 예를 들면 위의 2번째 표에서 [P,Y]의 값은 'CAP'와 'ACAY'를 비교한 값이 오게 되고, 'P'와 'Y'는 다르기 때문에 'CA'와 'ACAY'의 LCS의 길이와 'CAP'와 'ACA'의 LCS의 길이중 큰 값이 오게된다. 

즉 표의 값을 구하는 규칙은 다음과 같다.

1. String1[n], String2[k]가 같다면 : [n, k] == [n-1, k-1] + 1

2. String1[n], String2[k]가 다르면 : [n, k] == [n-1, k]와 [n, k-1] 중 큰 값

소스에서는 dp배열을 이차원으로 생성하여 -1로 초기화시켜 갱신된 값인지 확인할 수 있도록 하였다. 이 때 주의할점은 0으로 초기화 하지 않아야되는데, 이는 위의 예제에서도 봤듯이 lcs가 0인 부분이 있어 잘못계산될 수 있기 때문이다.

그다음 lcs(int i, int j) 함수 -> [i와j는 행과 열을 뜻한다] 를 생성하여 값을 확인하며 재귀함수를 돌렸다.

string을 비교하는 작업에서 lcs가 작은 값을 가져갈 필요가 없기때문에 max값을 리턴하도록 하였다.

소스링크

출처: http://twinw.tistory.com/126 [흰고래의꿈]