두 개의 문자열 s와 t가 주어졌을 때, 두 문자열을 모두 부분 수열(subsequence)로 포함하는 가장 짧은 문자열, 즉 최단 공통 초수열(Shortest Common Supersequence)의 길이를 구하는 문제입니다.
예를 들어 입력이 s = "pipe", t = "people"이라면 출력은 7이 됩니다. 이 경우 가능한 초수열 중 하나는 "pieople"입니다.
해결 접근 방법
이 문제는 최장 공통 부분 수열(LCS, Longest Common Subsequence)을 활용하면 효율적으로 해결할 수 있습니다. 두 문자열 길이의 합에서 LCS의 길이를 빼면, 공통되는 부분은 한 번만 포함되고 나머지 문자들은 각각 이어 붙여진 최단 초수열의 길이를 얻을 수 있습니다.
동적 계획법(DP)을 적용하는 단계는 다음과 같습니다.
m := 문자열 s의 길이, n := 문자열 t의 길이
(m + 1) × (n + 1) 크기의 2차원 테이블을 생성하고 모든 값을 0으로 초기화합니다.
i를 0부터 m까지 반복합니다.
j를 0부터 n까지 반복합니다.
i가 0이거나 j가 0이면 table[i][j] = 0으로 설정합니다.
그렇지 않은 경우,
s[i - 1]과 t[j - 1]이 같으면 table[i][j] = 1 + table[i - 1][j - 1]로 갱신합니다.
다르면 table[i][j] = max(table[i][j - 1], table[i - 1][j])로 설정합니다.
최종적으로 m + n − table[m][n]을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 더 자세히 이해할 수 있습니다.
class Solution: def solve(self, s, t): m = len(s) n = len(t) table = [[0 for i in range(n + 1)] for j in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: table[i][j] = 0 else: if s[i - 1] == t[j - 1]: table[i][j] = 1 + table[i - 1][j - 1] else: table[i][j] = max(table[i][j - 1], table[i - 1][j]) return m + n - table[m][n] ob = Solution() s = "pipe" t = "people" print(ob.solve(s, t))
입력
"pipe", "people"
출력
7
복잡도 분석
이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(m × n)입니다. 두 문자열의 모든 문자 쌍에 대해 DP 테이블을 한 번씩 채우기 때문입니다.