[백준/Swift] 5582: 공통 부분 문자열, LongestCommonSubsequence, LongestCommonSubstring차이 | PS일지

문제

5582번: 공통 부분 문자열

간단한 문제 요약

두 문자열이 주어졌을 때 공통으로 가장 긴 부분 문자열의 길이를 출력하시오.

고려해야 할 사항

Longest Common Subsequence VS Longest Common Substring 의 개념을 알면 좋은 것 같습니다. 

전자의 경우 공통으로 있는 문자열들의 가장 긴 수열을 의미합니다. 후자의 경우 공통으로 있는 연속된 문자열들 중 가장 긴 문자열을 의미합니다.

 

예를들어

문자열1: ABACD

문자열2: ABTCD

LCSubsequence의 경우 ABCD // 공통으로 존재함 (굳이 연속되지 않아도 됨)

LCSubstring의 경우 AB or CD입니다. // 연속

문제 풀이

이 문제에선 어떤 문자열의 부분 문자열이란 연속으로 나타나야 한다고 정의되어 있습니다. ABRACADABRA의 부분 문자열 중 ABRC는 부분 문자열이 아니라고 합니다. (LCSubsequence x). 그래서 LCSubstring을 구하는 문제입니다.

 

공통 부분 문자열을 구할 때 문자열1의 각각의 문자에 대해 문자열2의 모든 문자열과 비교하면서 공통 부분 문자열을 찾아갑니다.

문자열1: ABACD

문자열2: ABTCD

 

문자열1의 A는 문자열2 A B T C D에서 일치하는 경우가 있는가?

일치, 불일치 조건을 이차원 배열에 저장합니다. (세로: 문자열1 길이 만큼의 배열길이, 가로: 문자열2 만큼의 배열길이)

	A	B	T	C	D
A	1	0	0	0	0

일치한다면 이차원 배열에 저장합니다. table에서 1은 문자열 2의 문자열 들 중에 문자열1의 A 문자열은 문자열2 문자열의 A문자열과 공통으로 존재한다는 것을 알 수 있습니다. 그리고 테이블에는 특정 위치일 때 ex) table[1][1]일 때

문자열1 AB  A...

문자열2 AB  T... 공통 부분 문자열 최대 길이를 저장합니다. == 2.

문자열1의 A다음 B는 문자열2 A B T C D에서 일치하는 경우가 있는가?

A B T C D

B

A	B	T	C	D
B

불일치.

 

A	B	T	C	D
	B

일치합니다.

	A	B	T	C	D
A	1	0	0	0	0
B	0	?

여기서 table의 ? 위치에는 어떤 값이 들어가야 하나 생각을 해야 합니다. 문자열2 ABTCD에서 두번째(index==1) 단어 B. 그리고 문자열1 ABACD에서 두번째(index==1) 단어 B. 각각의 문자열은 동일한 문자열입니다. 그리고 공통 문자열임을 기록하기 위해, "공통 부분 문자열"인지 확인하기 위해서는 현재 탐색중인 각각의 index -1("각각의 특정 문자 B 이전의 문자가 얼만큼 공통 문자인가?")을 한 결과를 확인하면 됩니다. 문자열2의 현재 탐색중인 str2[1 - 1] == A . str1[1-1] == A. str2[0] == str1[0]이므로 이전 문자열 또한 A로 동일함을 알 수 있습니다. 

	A	B	T	C	D
A	1	0	0	0	0
B	0	2

문자열1 의 A의 경우

	A	B	T	C	D
A	1	0	0	0	0
B	0	2	0	0	0
A	1	0	0	0	0

문자열1의 C의 경우

	A	B	T	C	D
A	1	0	0	0	0
B	0	2	0	0	0
A	1	0	0	0	0
C	0	0	0	1	0

문자열1의 D의 경우

	A	B	T	C	D
A	1	0	0	0	0
B	0	2	0	0	0
A	1	0	0	0	0
C	0	0	0	1	0
D	0	0	0	0	2

이렇게 문자열1, 문자열2에서 AB, CD가 가장 긴 부분 문자열임을 알 수 있습니다.

문자열1 == ABTD

문자열2 == ABCT

	A	B	T	D
A	1	0	0	0
B	0	2	0	0
C	0	0	0	0
T	0	0	1	0

이 경우는 이렇게 테이블이 채워집니다. AB, T 이렇게 공통 부분 문자열입니다. 최대를 찾기 위해선 table전체를 확인해야 합니다. 그게 아니면 table에 값을 저장할 때 최대 값을 갱신하는 방법이 있습니다.

 

여기까지 table에 0이아닌 값을 증가시키는 경우는 특정 index일 때 문자열1의 특정문자str1[index], 문자열2의 특정문자str2[index]가 같아야지만 각각의 그 이전 단어일 때str1[index-1], str2[index-1]일 때 부분 문자열 최대 길이정보를 가진 기록을 사용하면 되고 그것은 table에 memoization방법으로 저장했기 때문에 곧바로 알 수 있습니다.

for i in 0..<str1.count {
	for j in 0..<str2.count {
    	if str1[i] == str2[j] {
            table[i][j] = table[i-1][j-1] + 1
        }
    }
}

Longest common substring의 경우 특정 index일 때 두 문자열의 단어가 일치하다면 각각의 이전 문자열의 부분 문자열 길이 기록을 활용합니다. 반면 Longest common subsequence는 부분 문자열이 '연속'적이 아니어도 되기에 특정 index에서 부분 문자열 길이가 갱신된다면 끝까지 유지시킵니다..?..

	A	B	T	D
A	1	1	1	1

문자열 A 비교

	A	B	T	D
A	1	1	1	1
B	1

문자열 B 비교 ...  왜 1이냐면 ABTD의 A는 B와 일치하지 않지만 B의 앞 단어 A와는 일치하기 때문입니다.

	A	B	T	D
A	1	1	1	1
B	1	2

그리고 ABTD의 B와 B가 일치하고 그 이전에 일치했던 길이 + 1.

	A	B	T	D
A	1	1	1	1
B	1	2	2	2

ABTD 의 T는 B와 일치하지 않지만 그럼에도 ABTD와 AB에서 LCS는 2임을 유지시킵니다....

코드

func solution() {
    let str1 = readLine()!.map{String($0)}
    let str2 = readLine()!.map{String($0)}
    var cache = Array(repeating: Array(repeating: 0, count: str2.count+1), count: str1.count+1)
    var res = 0
    defer{ print("\(res)") }
    (1...str1.count).map{
        for j in 1...str2.count where str1[$0-1]==str2[j-1] {
            cache[$0][j] = cache[$0-1][j-1] + 1
            res = max(res,cache[$0][j])
        }
    }
}
solution()