9252. LCS 2 (Python)

9252번: LCS 2

 

풀이

 LCS를 구하는 알고리즘(참고)을 그대로 적용하여 해결하면 된다. 추가적으로 최장 길이에 해당하는 문자열도 구해야 하는데 추가적으로 2차원 리스트를 하나 만들어서 문자열을 기록해 나가면 된다. 생각해 보니까 걍 2차원 리스트 하나만 써도 돼서 하나만 썼다. dp 배열 하나만 쓰고 여기에 문자열을 기록하고 길이는 len()을 사용했다.

 

 두 문자열 A와 B가 있을 때 A의 i번째 문자와 B의 j번째 문자가 같다면 dp[i][j]에는 dp[i-1][j-1] + 1이 기록된다. 문자열을 기록하는 리스트 dpStr[i][j]에는 dpStr[i-1][j-1]의 문자열에 A의 i번째 문자(또는 B의 j번째 문자)를 추가해 준다. 두 문자가 다르다면 dp[i][j-1]와 dp[i-1][j]의 값 중 큰 값을 dp[i][j]에 기록하는데 dpStr[i][j] 역시 큰 값을 갖고 있는 쪽의 문자열을 갖고 와 기록하면 된다.

 

 위와 같은 과정을 마치고나면 dpStr[i][j]에 두 문자열의 LCS가 기록된다.

 

코드

if __name__ == '__main__':
    A = input()
    B = input()

    # dp[i][j] : A의 i번째까지의 문자열과 B의 j번째까지의 문자열의 LCS
    dp = [['' for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]

    for i in range(1, len(A) + 1):
        nowA = A[i-1]
        for j in range(1, len(B) + 1):
            nowB = B[j-1]

            if nowA == nowB:  # 두 문자가 같을 경우
                dp[i][j] = dp[i-1][j-1] + nowA
            else:  # 두 문자가 다를 경우
                if len(dp[i][j-1]) > len(dp[i-1][j]):
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = dp[i-1][j]

    print(len(dp[len(A)][len(B)]))

    if len(dp[len(A)][len(B)]) != 0:
        print(dp[len(A)][len(B)])

 

(수정 전 코드)

if __name__ == '__main__':
    A = input()
    B = input()

    # dp[i][j] : A의 i번째까지의 문자열과 B의 j번째까지의 문자열의 LCS 길이
    # dpStr[i][j] : A의 i번째까지의 문자열과 B의 j번째까지의 문자열의 LCS
    dp = [[0 for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]
    dpStr = [['' for _ in range(len(B) + 1)] for _ in range(len(A) + 1)]

    for i in range(1, len(A) + 1):
        nowA = A[i-1]
        for j in range(1, len(B) + 1):
            nowB = B[j-1]

            if nowA == nowB:  # 두 문자가 같을 경우
                dp[i][j] = dp[i-1][j-1] + 1
                dpStr[i][j] = dpStr[i-1][j-1] + nowA
            else:  # 두 문자가 다를 경우
                if dp[i][j-1] > dp[i-1][j]:
                    dp[i][j] = dp[i][j-1]
                    dpStr[i][j] = dpStr[i][j-1]
                else:
                    dp[i][j] = dp[i-1][j]
                    dpStr[i][j] = dpStr[i-1][j]

    print(dp[len(A)][len(B)])

    if dp[len(A)][len(B)] != 0:
        print(dpStr[len(A)][len(B)])