두 개의 소문자 문자열 s와 t가 있다고 가정해 보겠습니다. 이때 우리는 두 문자열 중 어느 한쪽에서든 임의의 문자를 삭제할 수 있는 연산을 수행할 수 있습니다. 목표는 s와 t를 완전히 동일하게 만들기 위해 필요한 최소 연산(삭제) 횟수를 찾는 것입니다.
예를 들어, 입력이 s = "pipe", t = "ripe"라고 한다면 출력은 2가 됩니다. s에서 'p'를, t에서 'r'을 각각 삭제하면 두 문자열이 모두 "ipe"로 같아지기 때문입니다.
풀이 접근 방식
이 문제는 최장 공통 부분 수열(LCS)과 밀접한 관련이 있습니다. 두 문자열에서 공통으로 유지할 수 있는 문자를 제외한 나머지를 모두 삭제하면 되므로, 정답은 다음과 같이 표현할 수 있습니다.
(s의 길이 + t의 길이) − 2 × LCS(s, t)
이를 해결하기 위해 다음과 같은 단계를 따릅니다.
- m := s의 길이
- n := t의 길이
- dp(i, j) 함수를 정의합니다. 이 함수는 s의 i번째 위치와 t의 j번째 위치부터 고려할 때 필요한 최소 삭제 횟수를 반환합니다.
- i가 m과 같다면, 즉 s를 모두 소진했다면 남은 t의 문자만큼 삭제해야 하므로 n − j를 반환합니다.
- j가 n과 같다면, 즉 t를 모두 소진했다면 마찬가지로 m − i를 반환합니다.
- 그 외의 경우:
- s[i]와 t[j]가 같다면 두 문자를 모두 유지하고 dp(i + 1, j + 1)을 반환합니다.
- 같지 않다면 둘 중 하나를 삭제해야 하므로 1 + min(dp(i + 1, j), dp(i, j + 1))을 반환합니다.
- 메인 메서드에서는 dp(0, 0)을 반환합니다.
구현 예시
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(s, t):
m = len(s)
n = len(t)
def dp(i, j):
if i == m:
return n - j
elif j == n:
return m - i
else:
if s[i] == t[j]:
return dp(i + 1, j + 1)
else:
return 1 + min(dp(i + 1, j), dp(i, j + 1))
return dp(0, 0)
s = "pipe"
t = "ripe"
print(solve(s, t))입력
"pipe", "ripe"
출력
2
성능 개선 팁
위 재귀 구현은 최악의 경우 O(2^n)에 가까운 시간이 걸릴 수 있습니다. 실무에서는 functools.lru_cache 데코레이터를 활용해 메모이제이션을 적용하거나, 반복문 기반의 동적 계획법(DP) 테이블로 변환하면 시간 복잡도를 O(m × n)까지 줄일 수 있습니다.