91. Decode Ways

💡 풀이

var numDecodings = function (s) {
  if (s.length > 0 && s[0] === '0') return 0;
  if (s.length < 2) return 1;

  // 만약 두 자리를 확인해야 할 때,
  // 숫자가 26 이하라면 1
  if (s[0] === '1' || (s[0] === '2' && parseInt(s[1]) < 7)) {
    
      
  // ex) 경우의 수: F(26) === F(2) + F(6) + F(26) 반면, 26(Z)은 조건에 포함되기 때문에, 
  // 아래와 같이 각 자리에 해당하는 경우의 수 (1)를 더해주고, 자기 자신(26)에 해당하는 경우의 수 (1)를 더해서, F(26) === 2이 된다.
  //   
   
    return numDecodings(s.slice(1)) + numDecodings(s.slice(2));
  }
  // 그게 아니고 26보다 크거나 한 자리수라면
  // ex) 경우의 수: F(32) === F(3) + F(2) 라는 규칙이 나오게 된다. 
  //이 경우, 한 자리수에 해당하는 경우의 수는 무조건 1이다. 따라서 F(32) === 1이다.
  return numDecodings(s.slice(1));
};

// 따라서 위의 코드를 재귀적으로 호출하면 답은 나오지만, 시간 초과가 된다. 
// 따라서 이미 찾았던 값은 memoization을 통해 해당 값을 기억했다가 가져올 수 있어야 한다.(다시 탐색하는 것이 아니라) 
// 이 말은 DP를 사용해야 한다는 뜻이다.

// 다른 사람의 풀이 (DP)
function numDecodings(s) {
  if (s == null || s.length === 0) return 0;
  if (s[0] === '0') return 0;

  const dp = new Array(s.length + 1).fill(0);

  dp[0] = 1;
  dp[1] = 1;

  console.log('dp: ', dp);

  for (let i = 2; i <= s.length; i++) {
    // 한 자리수
    const a = Number(s.slice(i - 1, i));
    if (a >= 1 && a <= 9) {
      dp[i] += dp[i - 1];
    }

    // 두 자리수
    const b = Number(s.slice(i - 2, i));
    if (b >= 10 && b <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  console.log('dp: ', dp);

  return dp[s.length];
}

let s = '221221312512510126';
numDecodings(s);

📝 정리

혼자서 해결하지 못한 DP 문제였다. 맨 위의 코드는 답은 구할 수 있지만 시간 초과로 실패한 코드다. 이렇게 시간을 초과하게 된다면 이미 찾았던 값은 기억을 해두는 DP를 사용해 시간을 줄여야 한다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/decode-ways/

LeetCode GitHub

https://github.com/tTab1204/LeetCode