JavaScript로 두 문자열을 동일하게 만드는 최소 ASCII 삭제 합 구하기

문제 정의

영어 소문자로만 이루어진 두 개의 문자열 str1과 str2를 각각 첫 번째, 두 번째 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수의 목표는 두 문자열을 완전히 동일하게 만들기 위해 삭제해야 하는 문자들의 ASCII 값 합계 중 최솟값을 찾아 반환하는 것입니다.

예를 들어, 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

입력

const str1 = 'sea';
const str2 = 'eat';

출력

const output = 231;

출력 결과 해설

"sea"에서 문자 "s"를 삭제하면 "s"의 ASCII 값인 115가 합계에 더해집니다.

"eat"에서 문자 "t"를 삭제하면 116이 합계에 추가됩니다.

그 결과 두 문자열은 모두 "ea"로 동일해지며, 115 + 116 = 231이 두 문자열을 같게 만들 수 있는 최소 합계입니다.

구현 코드

다음은 동적 계획법(Dynamic Programming)을 활용한 전체 코드입니다 −

const str1 = 'sea';
const str2 = 'eat';
const minimumSum = (str1 = '', str2 = '') => {
   const chartCode = (s = '') => {
      let code = 0
      for (const c of s) {
         code += c.charCodeAt(0)
      }
      return code
   }
   let prev = new Array(str2.length + 1).fill(0)
   for (let ind1 = str1.length; ind1 >= 0; ind1--) {
      const current = new Array(str2.length + 1).fill(0)
      for (let ind2 = str2.length; ind2 >= 0; ind2--) {
         if (ind1 === str1.length) {
            current[ind2] = chartCode(str2.slice(ind2))
         } else if (ind2 === str2.length) {
            current[ind2] = chartCode(str1.slice(ind1))
         } else if (str1[ind1] === str2[ind2]) {
            current[ind2] = prev[ind2 + 1]
         } else {
            current[ind2] = Math.min(
               prev[ind2] + (str1[ind1]).charCodeAt(0),
               current[ind2 + 1] + (str2[ind2]).charCodeAt(0),
            )
         }
      }
      prev = current
   }
   return prev[0]
}
console.log(minimumSum(str1, str2));

동작 원리

이 솔루션은 바텀업 방식의 동적 계획법을 활용합니다. 핵심 로직은 다음과 같습니다.

prev와 current라는 두 개의 1차원 배열을 사용해 메모리 사용량을 줄입니다.
두 문자열을 뒤에서부터 순회하며, 현재 위치의 문자가 서로 같다면 이전 단계의 최적 값을 그대로 가져옵니다.
문자가 다르다면, 한쪽 문자열의 문자를 삭제하는 두 가지 경우 중 ASCII 합이 더 작은 쪽을 선택합니다.
한쪽 문자열이 끝에 도달한 경우에는 남은 문자열 전체의 ASCII 합을 더해줍니다.

이러한 방식으로 모든 부분 문제를 해결하면, 최종적으로 prev[0]에 저장된 값이 두 문자열을 동일하게 만들기 위한 최소 ASCII 삭제 합이 됩니다.