Python에서 삭제 된 숫자의 최소 자릿수 합계를 찾는 프로그램

<시간/>

두 개의 문자열 s와 숫자 t가 있다고 가정하고 문자열에서 숫자를 제거하는 방법을 찾아야 다음과 같이 됩니다. 1. 두 문자열이 동일합니다. 2. 삭제된 숫자의 합이 최소화됩니다. 마지막으로 최소화된 합을 반환합니다.

따라서 입력이 s ="41272" t ="172"와 같으면 첫 번째 문자열에서 "4"와 "2"를 제거하여 "172"를 얻을 수 있으므로 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

lcs() 함수를 정의합니다. 이것은, b, m, n
이 걸립니다.
table :=크기가 (n + 1) x (m + 1)이고 0으로 채워지는 2차원 행렬
범위 1에서 m에 있는 i에 대해 수행
- 범위 1에서 n까지의 j에 대해 수행
  - a[i - 1]이 b[j - 1]과 같으면
    - table[i, j] :=table[i - 1, j - 1] + 2 *(a[i - 1] - 48의 ASCII)
  - 그렇지 않으면
    - table[i, j] =table[i - 1, j]와 table[i, j - 1]의 최대값)
반환 테이블[m, n]
기본 방법에서 다음을 수행하십시오.
m :=a의 크기, n :=b의 크기
c :=0
0에서 m 사이의 i에 대해 수행
- c :=c + a[i]의 ASCII - 48
0에서 n 사이의 i에 대해 수행
- c :=c + b[i]의 ASCII - 48
결과 :=c - lcs(a, b, m, n)
반환 결과

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"