DCP: #7 [Abandoned]

Good morning! Here’s your coding interview problem for today.

This problem was asked by Facebook.

Given the mapping a = 1, b = 2, … z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message ‘111’ would give 3, since it could be decoded as ‘aaa’, ‘ka’, and ‘ak’.

You can assume that the messages are decodable. For example, ‘001’ is not allowed.

Status: Abandoned

// Solving, Solved, Abandoned, Pending

음, 숫자를 알파벳으로 디코딩하는 문제 같읍니다.
지금 제가 가진 지식만으로는 저 숫자들을 디코딩하는 알고리즘을 만들 수도 없다는 게 큰 난제입니다.
그나저나 여기 문제들은 다 어려운 건가요? Medium은 무슨 Easy도 어려워서 못 풀겠더만;
이번엔 또 어떤 삽질을 해야할 지 기대가 되네요^^

조언 받습니다만, 의도적인 정답코드 공개는 삼가 주시면 감사하겠습니다.

잘 생각해보면 한문자 또는 두문자로 나누면 되고,
0의 경우 좀 특수할거같고, 두문자로나눌때 첫글자도 조건이잇죠?

게다가 11이랑 111이랑 관계를 한번 생각해보시면 확장하는데 어떤식인지 생각나실수도 ㅎㅎㅎ

일단 제가 생각한 솔루션은
a를 아스키코드로 바꾸면 97이니까, 97을 상수로 정해두고 그 상수를 기준으로 왔다갔다 하는거죠.
여러개의 숫자를 쪼개는 기준은 z=26+97=123이니까 123 이하의 숫자들까지만 디코딩하고
예를 들어 341의 경우
34 1
3 41
3 4 1
이렇게 나눌 수 있지만 34+97와 41+97은 123을 초과했으니 첫번째, 두번째 방법은 제외해버리면 끝.
이런식으로 만들면 굳이 a부터 z까지 숫자를 할당해야할 필요는 없으니 좀 더 편해지겠네요.
기준은 정했으니 이제 쪼개기만 하면 되는데… 이거는 삽질좀 해야할 듯요.

image

?

Summary
def main():
    st = "111"
    st = "341"
    #st = "001"
    arr = list(map(int, st))
    n = solve(arr)
    print(n)


def solve(arr):
    print(arr)
    if len(arr) < 2:
        return 1

    a, b, *_ = arr
    n = 0
    if a != 0:
        n += solve(arr[1:])
    if 0 < a < 3 and 10*a + b <= 26:
        n += solve(arr[2:])
    return n


if __name__ == "__main__":
    main()

맞앗는지는 모름;

DCP 문제들이 초보가 풀기에는 난이도가 꽤 있는 거 같으니 (백준 실버 1-3 정도?) 못 푸시겠다면 백준 solved.ac 브론즈부터 위로 차근차근 올라오시는 걸 추천

문득 기억은 어렴풋이 나는데
로버트 세지윅 알고리즘 책에 저러한 케이스를 다루는 방법이 있엌ㅅ던것 같읍니다
더이상 스포하면 뭔가 스포쟁이 되는것 같아서…

1 Like

이건 좀 양심적이네여.

1 Like

그래야 겠네요 :joy:

Hint & sol

피보나치

27, 28, 29과 그 이상은 무조건 분리해서 생각해야함
-> 이것을 기준으로 앞과 뒤 경우의 수 계산 후 모두 곱하기

근데 덩어리 길이에 따른 경우의 수가 피보나치 수열을 이룬다.

유사문제

2591번: 숫자카드

Haskell

import Data.Char

solve :: String -> Int
solve = go . map digitToInt where
    go      []  = 1
    go (  _:[]) = 1
    go (x:y:zs) = go (y:zs) + if 10 * x + y <= 26 then go zs else 0
1 Like