문제 개요
숫자로만 이루어진 두 문자열 s와 t가 주어집니다. 각 문자열에서 일부 자릿수를 제거하여 다음 두 조건을 만족해야 합니다.
- 제거 후 두 문자열이 완전히 동일해야 합니다.
- 삭제된 자릿수들의 합이 최소가 되어야 합니다.
마지막으로 최소화된 삭제 합계를 반환하면 됩니다.
예를 들어 입력이 s = "41272", t = "172"라면 출력은 6입니다. 첫 번째 문자열에서 '4'와 '2'를 제거하면 "172"가 되고, 삭제된 숫자의 합은 4 + 2 = 6이기 때문입니다.
접근 방법: 가중치 적용된 LCS
이 문제는 최장 공통 부분 수열(Longest Common Subsequence) 알고리즘을 응용하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 두 문자열에 공통으로 남겨둘 수 있는 부분 수열 중, 자릿수의 합이 가장 큰 것을 찾습니다.
- 남긴 숫자는 삭제 대상이 아니므로, 전체 자릿수 합에서 (남긴 숫자 합 × 2)를 빼면 삭제되는 숫자의 최소 합이 됩니다.
DP 테이블에서 두 문자가 일치할 때 해당 숫자 값을 2배로 더하는 방식으로 이를 구현합니다.
알고리즘 단계
- lcs(a, b, m, n) 함수를 정의합니다.
- (m + 1) × (n + 1) 크기의 2차원 테이블을 생성하고 0으로 초기화합니다.
- i를 1부터 m까지 반복하면서, j를 1부터 n까지 반복합니다.
- a[i - 1]과 b[j - 1]이 같으면: table[i][j] = table[i - 1][j - 1] + 2 × (a[i - 1]의 숫자 값)
- 다르면: table[i][j] = max(table[i - 1][j], table[i][j - 1])
- table[m][n]을 반환합니다.
메인 로직
- m := a의 길이, n := b의 길이로 설정합니다.
- c := 0으로 초기화한 뒤, a와 b의 모든 자릿수 값을 더합니다.
- result := c − lcs(a, b, m, n)을 계산하여 반환합니다.
Python 예제 코드
아래 구현을 통해 더 쉽게 이해할 수 있습니다.
class Solution:
def lcs(self, a, b, m, n):
table = [[0 for i in range(n + 1)] for j in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 2 * (ord(a[i - 1]) - 48)
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
return table[m][n]
def solve(self, a, b):
m = len(a)
n = len(b)
c = 0
for i in range(m):
c += ord(a[i]) - 48
for i in range(n):
c += ord(b[i]) - 48
result = c - self.lcs(a, b, m, n)
return result
ob = Solution()
s = "41272"
t = "172"
print(ob.solve(s, t))
입력
"41272", "172"
출력
6
동작 원리 설명
위 예제에서 전체 자릿수의 합은 (4+1+2+7+2) + (1+7+2) = 16 + 10 = 26입니다. 두 문자열에 공통으로 남길 수 있는 최적 부분 수열은 "172"이며, 그 합은 10입니다. 따라서 삭제되는 숫자의 최소 합은 26 − 2 × 10 = 6이 됩니다.
이 알고리즘의 시간 복잡도는 O(m × n), 공간 복잡도 역시 O(m × n)으로, 두 문자열의 길이에 비례하여 효율적으로 동작합니다.