Algorithm | Decode Ways

본 글은 leetCode의 Decode Ways 문제 솔루션을 JavaScript 코드로 정리한 글입니다.

길이가 i인 문자열 s를 decode한 경우의 수를 D(i)라 하겠습니다.

D(i)의 값은 s[i]와 s[i - 1]에 따라 달라집니다.

D(i) = D(i - 1)

우선, s[i]가 "1"부터 "9" 사이의 값이라면 s[i]는 "a"부터 "i"에 각각 대응합니다.

1 2 3 4 5 6 7 8 9
a b c d e f g h i

그러므로, s[i] >= 1 && s[i] <= 9 라면 D(i)는 D(i - 1) 뒤에 a-i가 한 글자 붙여진 셈이 되며 경우의 수 또한 D(i - 1)의 값을 그대로 받게 됩니다.

JavaScript는 묵시적 형변환(Implicit Type Comversion)을 지원합니다. 숫자로 이뤄진 문자열과 수의 대소비교를 할 때에도 묵시적 형변환이 적용되어서 문자열을 숫자로 바꾼 뒤에 두 수의 대소비교를 합니다. 때문에 s[i] >= 1 && s[i] <= 9와 같은 대소비교가 가능합니다.

추가로 문제에 문자열 s가 0-9만을 포함한다는 제한사항을 이용하여 조건을 더 간결하게 만들 수 있습니다. 간결해진 조건으로 s[i] 값에 따른 D(i)와 D(i -1)의 관계를 표현하면 다음과 같습니다.

if(s[i] !== "0") D(i) = D(i - 1);

D(i) = D(i - 2)

s[i]는 단독으로 문자 a-i로 해독될 수도 있지만, 한편으론 s[i - 1]과 함께 문자 j-z로 해석될 수도 있습니다.

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z

이 경우엔 s[i - 1] + s[i]이 하나의 알파벳으로 해독되기 때문에 D(i)에 D(i - 2) 값을 더한 셈이 됩니다.

즉, s[i - 1] + s[i] >= 10 && s[i - 1] + s[i] <= 26을 만족하는 s[i - 1] + s[i]는 "j"부터 "z"까지 중 하나의 문자가 되어 D(i - 2)인 경우 뒤에 덧붙여지게 되는 것입니다.

마찬가지로 s[i - 1] + s[i] 값에 따른 D(i)와 D(i -1)의 관계를 표현하면 다음과 같습니다.

if(s[i - 1] + s[i] >= 10 && s[i - 1] + s[i] <= 26) D(i) = D(i - 2);

Dynamic Programming

지금까지 도출한 점화식을 바탕으로 Dynamic Programming을 활용한 정답 코드입니다.

var numDecodings = function(s) {
  let dp = [1];
  dp[1] = s[0] === "0" ? 0 : 1;

  for(let i = 1; i < s.length; ++i) {
    dp[i + 1] = 0;
    if(s[i] !== "0") dp[i + 1] += dp[i];
    if(s[i - 1] + s[i] >= 10 && s[i - 1] + s[i] <= 26) dp[i + 1] += dp[i - 1];
  }

  return dp[s.length];
};

우선 dp[i]는 길이가 i - 1인 문자열을 decode한 경우의 수입니다. 문자열의 길이보다 하나 더 큰 인덱스에 경우의 수를 저장하는 이유는 dp[0]을 별도의 값으로 활용하기 때문입니다.

알다시피, D(i)를 구하기 위해선 D(i - 1) 혹은 D(i - 2)의 값이 필요합니다. 이럴때 통상적으로는 s[0]과 s[1]를 참고하여 D(0)과 D(1) 값을 미리 구한 뒤에 i = 2부터 반복문을 시작합니다. 하지만, D(1) 또한 예외없이 i > 1인 D(i)와 똑같은 점화식이 적용되어 반복문에 포함하여 값을 구할 수 있으며, D(1)의 경우의 수를 일일히 코드로 지정하는 방법도 그리 바람직해보이지 않습니다.

대신, 반복문을 i = 1부터 시작하더라도 D(1)을 계산할 수 있도록 dp[0]에 더미 값을 넣어줘서 D(0)(dp[1])만 직접 지정해주면 그 이후의 값은 반복문을 통해 자동적으로 구해지도록 했습니다.

반복문 내부를 보면 다음과 같은 코드가 있습니다.

dp[i + 1] = 0;
if(s[i] !== "0") dp[i + 1] += dp[i];    // 조건 1
if(s[i - 1] + s[i] >= 10 && s[i - 1] + s[i] <= 26) dp[i + 1] += dp[i - 1];    // 조건 2

위 코드의 결과를 정리했습니다.

• 조건 1만 만족: dp[i + 1] = dp[i]
• 조건 2만 만족: dp[i + 1] = dp[i - 1]
• 조건 1과 조건 2를 모두 만족: dp[i + 1] = dp[i] + dp[i - 1]
• 조건 1과 조건 2를 모두 불만족: dp[i + 1] = 0

조건 1과 조건 2를 모두 불만족하는 예로는 "100"과 같은 경우가 있겠습니다. 해독을 할 수 없는 잘못된 문자열인 것이죠. "100"과 같은 잘못된 문자열이 도중에 껴있으면 나머지 부분이 아무리 제대로 된 암호문이더라도 해독할 수 없게 됩니다.

코드에서도 s[i]를 a-i로 해독하거나(조건 1) j-z로 해독하지(조건 2) 못하는 경우, 즉 s[i] = 0이고, s[i - 1] + s[i] 값이 0 이거나 26을 초과할 때 dp[i + 1] = 0 이 됩니다. dp[i + 1] = 0 일 때 반복문의 다음 실행에서 발생하는 결과를 정리하면 다음과 같습니다.

조건 1

• s[i + 1] === "0"이면, dp[i + 2] = 0
• s[i + 1] !== "0"이면, dp[i + 2] = dp[i + 2] + dp[i + 1] = 0 + 0 = 0

s[i + 1] 값에 상관없이 dp[i + 2] = 0이 됩니다.

조건 2

s[i + 1]의 값에 상관없이 s[i] + s[i + 1] < 10 이므로 dp[i + 2] = 0이 됩니다.

즉, 한 번 값이 0인 dp[i]가 등장하면 그 뒤에 오는 dp 값들은 모두 0이 되며 이를 통해 잘못된 문자열이 도중에 껴있을 때의 경우의 수도 구할 수 있습니다.

Back to top ↑