11056번: 두 부분 문자열 (LCS)

 

11056번: 두 부분 문자열

이 문제는 정말 모를때는 혼자 풀어보겠다고 몇시간을 투자하기 보다는 풀이를 찾아서 접근 방안과 새로운 이론이 필요하다면 그 이론을 공부할 필요가 있음을 알려주었다. 아직 기본적인 알고리즘과 자료구조에 대해 공부해야 할 점이 많다.

---

 문제에서 원하는 부분 문자열은 subsequence(연속적이지는 않은 부분 문자열) 인데 나는 substring(연속적인 부분 문자열) 으로 잘못 이해해서 부분 문자열을 substring으로 생각한 경우에 다음과 같이 코드를 짰다. 

A = input()
B = input()
s,l = (A,B) if len(A)<len(B) else (B,A)
def div(word,length):
    arr = []
    for i in range(len(word)-length+1):
        arr.append((i,word[i:i+length]))
    return arr
overlap = {}
x = '0'*len(s)
for i in range(2,len(s)+1):
    for index,word in div(s,i):
        if word in l:
            overlap[index] = word
for i in overlap:
    x = x[:i]+overlap[i]+x[i+len(overlap[i]):]
print(len(l)+len([i for i in x if i=='0']))

 

 

문제 예시에서 빨강을 backjoon 내 문자열, 파랑을 hongjun 내 문자열 형광색을 공통 부분 문자열로 나타냈다.

A = 'baekjoon', B = 'hongjun'인 경우, baekhongjouon 이다.

이때 j의 왼쪽에는 'b,a,e,k','h,o,n,g'가 각 문자열의 순서는 유지하되, 빨강과 파랑의 순서는 상관없다.. 

j와 n 사이에는 'o,o', 'u' 에서 빨강 내 순서, 파랑 내 순서는 유지하되 빨강과 파랑의 순서는 상관없다. 

baekhongjooun 으로 나타내도 상관이 없는 거다. j와 n에 대한 위치 관계만 만족하기만 하면 된다. 

공통 부분 문자열이 정해진 경우에는 이후 위치 관계는 각각 A,B의 순서는 유지하지만 A와 B 사이에는 관련이 없으므로 공통 부분 문자열의 최대 개수만 구하면 최소의 S 길이를 구할 수 있다. 

A' = aaaabbb, B' = ababab 일때 B를 저 상자들에 순서대로 끼워넣었을 때 각 상자에서 0번째 위치의 값과 1번째 이후의 값이 같은 경우가 있으면 공통 부분 문자열에 0번째 위치의 문자가 포함된다.   . 

각 상자에 들어갈 원소의 개수가 정해진다면 "abaaababbb"와 같이 문자들의 위치관계는 하나로 유일하게 정해진다. 따라서 중복조합으로 a1+a2+a3+..a_len(B') = len(A') 을 만족하는 (a1,a2,a3..,a_len(B')를 중복조합으로 구했다. 이후 각 상자에 있는 각각의 a'원소가 포함되는지 확인하여 공통문자열의 길이를 알아내었다.  하지만 시간초과가 뜬다. 중복조합으로 모든 경우를 체크를 하였기에 시간이 오래걸렸다. 최악의 경우 nHr 에서 n=1000, r=1000이므로 이만큼 반복하려면 당연히 1억번 연산안으로 끝낼 수 없었던 것이다. 최악의 경우가 아니더라도 굉장히 많은 연산 횟수를 필요로 한다.

from itertools import combinations_with_replacement
A = input()
B = input()
a = ""
b = ""
for i in A:
    if i in B:
        a += i
for i in B:
    if i in A:
        b += i
count = 0
for i in combinations_with_replacement(range(len(a)),len(b)) :
    cnt = 0
    arr = [""] * len(a)
    for j in range(len(i)):
        arr[i[j]]+=b[j]
    for k in range(len(arr)):
        if a[k] in arr[k]:
            cnt += 1
    if count < cnt:
        count = cnt
print(len(A)+len(B) - count)

---

여기서 몇 시간 동안 더 고민해보았으나 더이상의 풀이법이 생각나지 않아 검색해 풀이를 조금만 보기로 했다. 이 문제는 LCS(longest common subsequence) 문제라고 한다. 그래서 LCS에 대해 좀 더 알아봤고 결국 A와 B의 LCS를 구하기만 하면 이 문제는 해결됨을 알 수 있었다. 아래 블로그를 바탕으로 LCS를 구현해보았다. 

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

A = input()
B = input()
def solve(string_A,string_B):
    string_A = '0'+string_A
    string_B = '0'+string_B
    LCS = [[0]*(len(A)+1) for _ in range(len(string_B)+1)]
    for i in range(1,len(string_B)):
        for j in range(1,len(string_A)):
            if string_A[j] == string_B[i]:
                LCS[i][j] = LCS[i-1][j-1] + 1
            else:
                LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1])
    return LCS
lcs = 0
for i in solve(A,B):
    if lcs < max(i):
        lcs = max(i)
print(len(A)+len(B)-lcs)

 

누군가에겐 쉬운 문제일 수 있지만 이거 풀려고 이틀동안 수학문제, 학원 숙제하면서 틈틈히 계속 고민했었고 여러가지 아이디어를 도입해 시도를 해보았고 지금에서야 LCS라는 DP 알고리즘을 공부하면서 결국엔 풀어내니 뿌듯하다. 이 문제를 통해 정말 모를때는 혼자 무작정 고민해보기 보다는 풀이를 찾아서 힌트를 찾고 접근 방안과 새로운 이론이 필요하다면 그 이론을 공부할 필요가 있음을 알려주었다. 아직 기본적인 알고리즘과 자료구조에 대해 공부해야 할 점이 많기 때문에 PS 공부를 꾸준히 해야겠다.