[LeetCode] 91. Decode Ways

문제

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

Decode Ways - LeetCode

———————————————————————————

 

잠깐만

이것 또한 체크하고 더하면서 진행해볼까요?

———————————————————————————

 

코드

class Solution {
    func numDecodings(_ s: String) -> Int {
        var countFrom1: [Int] = Array(repeating: 0, count: s.count+1)
        var countFrom2: [Int] = Array(repeating: 0, count: s.count+1)
        countFrom1[0] = 1
    
        for index in 1...s.count {
            var indexFrom1 = index - 1
            if indexFrom1 >= 0 {
                countFrom1[index] = countFrom1[indexFrom1] + countFrom2[indexFrom1]
            }
        
            var indexFrom2 = index - 2
            if indexFrom2 >= 0 {
                countFrom2[index] = countFrom1[indexFrom2] + countFrom2[indexFrom2]
            }
        
            let number = Int(String(Array(s)[index-1...index-1]))
            if number == 0 {
                countFrom1[index-1] = 0
                countFrom1[index] = 0
                countFrom2[index-1] = 0
            }
            
            if index-2 >= 0, var tempNum = (Int(String(Array(s)[index-2...index-1]))), tempNum > 26 {
                countFrom2[index] = 0
            }
        }
        return countFrom1[s.count] + countFrom2[s.count]  
    }
}

———————————————————————————

 

설명

다른 깔끔한 로직이 있어보이는데,

우선, 직접 작성하며 발견한 로직대로, 구현한 코드를 설명하겠습니다.

키보드에서 임의로 입력한 숫자 입니다.

"13220238101213"

 

숫자는 1자리수로 인식하는 경우와 2자리수로 인식하는 경우가 존재합니다.

그래서, 바로 전 숫자(1칸 이전)에서 가져온 암호의 경우의 수를 입력하는 array를 만들어줬어요.

전전 숫자(2칸 이전)에서 가져온(숫자를 두자릿수로 인식한 경우) 암호의 경우의 수를 입력하는 array를 만들어줬어요.

하지만 두자리수 숫자중 불가능한 숫자가 존재합니다.

0으로 시작하는 숫자와 26을 넘어서는(초과) 숫자.

이에 대한 로직처리를 할거에요.

 

숫자 26을 초과하여, 2자리 숫자로 인식 불가능 한 경우

숫자를 1자리 숫자로 인식해야 합니다. 그럼 "2칸 이전"에서 가져온 경우의 수는 필요 없겠죠?

"2칸 이전"은 숫자 2자리로 인식할때의 경우의수이며, 2자릿수로 인식 불가능하기 때문에 필요가 없죠.

"2칸 이전"의 엘리먼트에 해당하는 값을 0으로 만들어줍니다.

예를 들어, 윗 그림에서 앞의 숫자 "132"가 보이죠?

132는 다음의 경우가 가능해요

[1, 3, 2], [1, 32], [13, 2]

하지만 숫자 32는 26을 초과하기 때문에 [1, 32]는 불가능 합니다.

세번째 숫자인 2의 경우의 수를 따져볼때,

첫번째 숫자(2칸 이전)인 숫자 1로부터 경우의 수를 가져오는건 불가능 하기 때문에, 0으로 만들어줍니다.

이해 되셨나요?

 

다음으로, 0이 존재하는 숫자는 반드시 10 또는 20입니다.

무조건 두자릿수의 숫자로 인식해줘야 합니다.

따라서, 0을 기준으로 경우의수를 따져볼때, 1칸 이전 숫자(바로 앞에 있는 숫자)에서 가져오는 경우의 수는 불가능 합니다.

따라서, 1칸 이전에서 가져온 경우의 수를 0으로 만들어줍니다.

또한, 0 앞에 있는 숫자 또한, 한자릿수 숫자로 인식 불가능하기 때문에(무조건 10 또는 20이니깐요),

경우의 수를 0으로 만들어줍니다.

0 앞에 있는 숫자를 기준으로 계산한 경우의수는 한자릿수로 숫자를 인식했을때의 경우의 수니깐 필요 없잖아요.

이렇게 로직은 끝났습니다. 코드로 구현해주면 되죠.

 

로그로 찍어봤어요.

 

다음은 로그를 포함한 코드 입니다.

//let nums = [2,7,9,3,1,5,3]
let s = "13220238101213"    //20
//let s = "12"    //2
//let s = "226"    //3
//let s = "06"    //0
//let s = "230"    //0

print(solution(s))

func solution(_ s: String) -> Int {
    print("")
    var countFrom1: [Int] = Array(repeating: 0, count: s.count+1)
    var countFrom2: [Int] = Array(repeating: 0, count: s.count+1)
    countFrom1[0] = 1
    
    for index in 1...s.count {
        print("체크 위치 :  ", terminator: " ")
        for space in 0..<index {
            print(" ", terminator: " ")
        }
        print("v")
        
        var indexFrom1 = index - 1
        if indexFrom1 >= 0 {
            countFrom1[index] = countFrom1[indexFrom1] + countFrom2[indexFrom1]
        }
        
        var indexFrom2 = index - 2
        if indexFrom2 >= 0 {
            countFrom2[index] = countFrom1[indexFrom2] + countFrom2[indexFrom2]
        }
        
        let number = Int(String(Array(s)[index-1...index-1]))
        if number == 0 {
            countFrom1[index-1] = 0
            countFrom1[index] = 0
            countFrom2[index-1] = 0
            
        }
            
        if index-2 >= 0, var tempNum = (Int(String(Array(s)[index-2...index-1]))), tempNum > 26 {
            countFrom2[index] = 0
        }
        
        print("입력 숫자 :    ", terminator: " ")
        s.forEach {
            print($0, terminator: " ")
        }
        print("")
        
        print("한칸 이전 :  ", terminator: " ")
        countFrom1.forEach {
            print($0, terminator: " ")
        }
        print("")
        
        print("두칸 이전 :  ", terminator: " ")
        countFrom2.forEach {
            print($0, terminator: " ")
        }
        print("")
        print("------------ ")
    }
    return countFrom1[s.count] + countFrom2[s.count]  
}

다음에 다른 코드를 생각하고 찾아봐서, 이해한 후 설명 해보겠습니다.

 

———————————————————————————

 

회고

역시 펜을 쥐고, 한번 쭉 작성해봐야 규칙을 알겠더라구요.

머리로 생각하다가, 노트에 끄적이니, 규칮을 찾을 수 있었어요.

DP라기 보단, 규칙 찾기 방식으로 보였어요. 다른 dp 방법을 생각해봐야겠어요.