[Leetcode] 91. Decode Ways

문제 요약

• 알고리즘 분류: 동적계획법(DP)
• 난이도: Medium
• 문제내용:
  • 숫자로된 문자열 S가 주어진다.
  • 1~26을 A ~ Z로 디코딩 가능하다.
  • 문자열에서 조합 가능한 가지수를 출력해라. 단 01 ~ 09은 안된다.
• 사이트 주소: https://leetcode.com/problems/decode-ways/description/

문제풀이

이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하기에는 시간이 많이 걸려서 시간이 최적화 되도록 풀어야한다. 그래서 이번문제는 DP로 해결할것이다. DP관련 자세한 설명은 아래 글로 확인 해보면된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

문제 접근방법

  dp는 구현보다 아이디어를 요구하는 문제로서 생각만 한다면 코드 구현은 간단한다.  우선 동적계획법관한 점화식 구하기 전에 안되는 조건이 몇개가 있다.

 일단 첫번째 자리가 0일경우다. 맨앞자리가 0이면 어떤한 조합이 불가능 하기때문에 경우의 수를 0반환 해야 한다.

그 멘위 경우빼고 가능한 경우 3가지를 보면 된다.

1.  0
2. 1~9
3. 10~26

0일 경우

0일 경우에는 뒤에 어떤 한 수가 와도 조합이 불가능하다. 하지만 0뒤에 숫자가 1, 2 숫자가 오면 조합이 되지만 그경우는 10~26에서 확인 해보자. 일단 인덱스가 0이면 경우의 수를 0으로 해야한다.

1~9일 경우

1에서 9는 어떤한 경우가 와도 다 가능하기때문에 이전 경우의 수를 그대로 옮겨 주면된다.

10~26 일 경우

이것은 경우의 수가 추가 되었다고 보면 된다. 그래서 이전것을 추가해주면 된다. 그러면 자리수가 0이여도 10, 20이 되니 되는 경우를 포함 하면 된다.

 

위 경우 3가지봤을때 모든 자리수가 3~9이면 1로 나오지만 10~26 경우만 추가만 해주는 작업 만 하면된다. 그래서 점화식은 아래와 같이 나타 낼수 있다.

1.  s[i] = 0 : dp[i] = 0
2. s[i] in (1 ~ 9) : dp[i] = dp[i-1]
3. s[i] + s[i-1] in (10~26):  dp[i] += dp[i-2]

우선 0으로 모든 값을 초기화 하고 0, 1을 1로 해주면 된다. 0으로 1로 해야 하는 이유는 i-2를 계산하기 위한 임시 값이라고 보면된다.. 1, 2번 경우의 수는 0일때 분기 처리 하면 되지만3일 경우에는 1,2경우에 추가만 해주면 된다. 그러면 시간 복잡도는 O(N)만큼 나올 것이다.

Code

Python

class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == '0': return 0

        length = len(s)
        dp = [0] * (length + 1)
        dp[0], dp[1] = 1, 1

        for i in range(2, length + 1):
            nowNum = int(s[i-2: i])

            if(s[i-1] != '0'):
                dp[i] += dp[i-1]

            if(10 <= nowNum <= 26):
                dp[i] += dp[i-2]

        return dp[length]

Java

class Solution {
    public int numDecodings(String s) {
		 
		if(s.charAt(0) == '0') return 0;
		 
		int lenth = s.length();
		int[] dp = new int[lenth + 1];
		 
		Arrays.fill(dp, 0); // 0으로 초기화
		 
		dp[0] = 1;
		dp[1] = 1;
		 
		 
		int nowNum;
		 
		 
		for(int i = 2; i <= lenth; i ++) {
			 
			nowNum = Integer.parseInt(s.substring(i-2, i));
			 
			if(s.charAt(i-1) != '0'){
				dp[i] += dp[i-1];
			}
			 
			if(10<= nowNum && nowNum <= 26) {
				dp[i] += dp[i-2];
			}
			  
		 }
	
		 System.out.println(Arrays.toString(dp));
		 return dp[lenth];
	 }
}