문제 설명
두 개의 문자열 s와 t가 주어졌을 때, 다음과 같은 방식으로 새로운 문자열을 만들려고 합니다.
- s에서 비어 있지 않은(non-empty) 부분 수열 sub1을 선택합니다.
- t에서 비어 있지 않은 부분 수열 sub2를 선택합니다.
- sub1과 sub2를 이어 붙여 하나의 문자열을 완성합니다.
이때 만들 수 있는 가장 긴 회문(palindrome)의 길이를 구하는 것이 목표입니다. 어떤 회문도 만들 수 없다면 0을 반환합니다.
예를 들어 s = "hillrace", t = "cargame"이라면 정답은 7입니다. s에서 "race"를, t에서 "car"를 가져와 이어 붙이면 "racecar"라는 길이 7의 회문을 만들 수 있기 때문입니다.
접근 방법: 동적 계획법(DP)
핵심 아이디어는 두 문자열을 하나로 합친 뒤 전체 문자열에 대해 '가장 긴 회문 부분 수열'을 구하되, 회문의 양 끝 문자가 서로 다른 문자열(s와 t)에서 와야 한다는 조건을 추가하는 것입니다. 그래야 s와 t 양쪽에서 최소 한 글자씩 사용했다는 문제의 요구 사항이 자연스럽게 충족됩니다.
구체적인 절차는 다음과 같습니다.
- n := s의 길이, m := t의 길이로 설정합니다.
- word := s + t (두 문자열을 연결한 문자열)
- (n+m) × (n+m) 크기의 2차원 배열 dp를 만들고 모든 값을 0으로 초기화합니다.
- i를 n+m-1부터 0까지 감소시키며, j를 i부터 n+m-1까지 증가시키며 반복합니다.
- i == j이면 dp[i][j] := 1 (길이 1짜리 회문)
- word[i] == word[j]이면 dp[i][j] := 2 + dp[i+1][j-1]
- 그 외에는 dp[i][j] := max(dp[i+1][j], dp[i][j-1])
- ans := 0으로 초기화한 뒤, i를 0부터 n-1까지, j를 m-1부터 0까지 감소시키며 반복합니다.
- s[i] == t[j]이면 ans := max(ans, dp[i][n+j])로 갱신합니다.
- ans를 반환합니다.
예제 코드 (Python)
def solve(s, t):
n, m = len(s), len(t)
word = s + t
dp = [[0] * (n + m) for _ in range(n + m)]
for i in range(n + m - 1, -1, -1):
for j in range(i, n + m):
if i == j:
dp[i][j] = 1
elif word[i] == word[j]:
dp[i][j] = 2 + dp[i + 1][j - 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
ans = 0
for i in range(n):
for j in range(m - 1, -1, -1):
if s[i] == t[j]:
ans = max(ans, dp[i][n + j])
return ans
s = "hillrace"
t = "cargame"
print(solve(s, t))입력
s = "hillrace"
t = "cargame"
출력
7
동작 원리와 복잡도
마지막 단계에서는 시작 인덱스 i가 s 영역(0 ≤ i < n)에 속하고, 끝 인덱스 n+j가 t 영역(n ≤ n+j < n+m)에 속하는 경우만 골라 답을 갱신합니다. 이렇게 하면 회문의 양 끝이 반드시 서로 다른 문자열에서 온 것이 보장되므로, s와 t 양쪽에서 비어 있지 않은 부분 수열을 사용했다는 조건이 만족됩니다.
시간 복잡도와 공간 복잡도는 모두 O((n+m)²)입니다. 두 문자열이 수천 자 수준이라도 충분히 실용적인 속도로 동작합니다.