백준 9252 LCS2 파이썬

dasd412·2022년 5월 24일
0

코딩 테스트

목록 보기
40/71

문제 설명

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력 조건

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력 조건

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.


전체 코드

import sys

str1 = sys.stdin.readline().rstrip()
str2 = sys.stdin.readline().rstrip()

arr = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]
for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):
        # 만약 첫 문자열 i 번째와 두 번째 문자열 j 번째가 같다면, 현재까지의 최장 공통 부분 수열 +1
        if str1[i - 1] == str2[j - 1]:
            arr[i][j] = arr[i - 1][j - 1] + 1
        # 다르다면, 세로 기준으로 비교한 것과 가로로 비교한 것 중 더 큰 값을 고른다.
        else:
            arr[i][j] = max(arr[i][j - 1], arr[i - 1][j])

answer = 0
for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):
        answer = max(answer, arr[i][j])

print(answer)

if answer > 0:
    string_list = []
    i = len(str1)
    j = len(str2)

    while arr[i][j] != 0:
        if arr[i][j] == arr[i - 1][j]:
            i -= 1
        elif arr[i][j] == arr[i][j - 1]:
            j -= 1
        else:
            string_list.append(str1[i - 1])
            i -= 1
            j -= 1

    for a in range(len(string_list)-1, -1, -1):
        print(string_list[a], end='')

참고

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#%EC%B5%9C%EC%9E%A5-%EA%B3%B5%ED%86%B5-%EB%B6%80%EB%B6%84%EC%88%98%EC%97%B4longest-common-subsequence-%EC%B0%BE%EA%B8%B0

profile
아키텍쳐 설계와 테스트 코드에 관심이 많음.

0개의 댓글