[인프런] 알파코드

문제

철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암
호화를 할 것인지 의논을 하고 있다.
영희 : 우리 알파벳 A에는 1로, B에는 2로 이렇게 해서 Z에는 26을 할당하여 번호로 보내기
로 하자.
철수 : 정말 바보같은 생각이군!! 생각해 봐!! 만약 내가 “BEAN"을 너에게 보낸다면 그것을 암
호화하면 25114이잖아!! 그러면 이것을 다시 알파벳으로 복원할 때는 많은 방법이 존재하는
데 어떻게 할건데... 이것을 알파벳으로 바꾸면 BEAAD, YAAD, YAN, YKD 그리고 BEKD로
BEAN말고도 5가지나 더 있군.
당신은 위와 같은 영희의 방법으로 암호화된 코드가 주어지면 그것을 알파벳으로 복원하는데
얼마나 많은 방법인 있는지 구하세요.

입력

첫 번째 줄에 숫자로 암호회 된 코드가 입력된다.
단, 코드는 0으로 시작하지 않으며, 코드의 길이는 최대 50이다. 0이 입력되면 입력 종료를 의미한다.
e.g)
25114

출력

입력된 코드를 알파벳으로 복원하는데 몇 가지의 방법이 있는지 각 경우를 출력한다. 그 가지수도 출력한다. 단어의 출력은 사전순으로 출력한다.
e.g)
BEAAD
BEAN
BEKD
YAAD
YAN
YKD
6

생각

• 파이썬의 ascii_uppercase 라이브러리를 사용하여 각 알파벳을 숫자와 매칭하는 딕셔너리를 생성하여 마지막에 출력에 사용할 수 있도록 하자.
• 모든 숫자를 각각 탐색 또는 index + 1로 탐색을 모든 알파벳에 대해 진행해야하기 때문에 DFS를 사용하여 구현하자.
• 결과값을 저장할 수 있는 리스트를 생성하고, dfs 함수에 해당 리스트의 position(index)를 함께 넘겨줘 탐색하도록 하자.
• 1~26까지의 숫자 중 일의 자리 숫자와 10의자리 숫자를 조건을 나누어 탐색하되, 각 조건에서 불필요한 조것을 cut-edge 할 수 있는지 생각해보자
  • 예를 들어, i가 23이면 두자릿수의 숫자이며, 23을 10으로 나눈 몫과 나머지를 활용하여 입력으로 주어진 숫자에 부합하는지 확인할 수 있다.
• 두자릿수의 경우 dfs 함수를 호출할 때, 다음의 인덱스를 넘겨줄 때 주의해서 넘겨주자. 바로 다음 인덱스가 아닌 +2값을 넘겨주어야 한다.
  • 23의 경우 23이 하나의 숫자가 되기 때문에 23 다음의 숫자를 탐색해야한다.
  • 이 경우에 주어진 숫자가 1~2라면 주어진 숫자보다 +1까지 탐색하여 IndexError가 발생한다. 이에 따른 예외처리를 해주자. 앞자리수가 3 이상이라면 알파벳 26개의 범위에 넘어서기 때문에 Index 범위에 벗어나게 탐색을 하지 않는다.

Solution

from string import ascii_uppercase

code = [int(n) for n in input()]
ret = [0] * len(code)
alpha_dict = dict()
cnt = 0

for i, k in enumerate(ascii_uppercase):
    alpha_dict[i+1] = k


# position: ret index
def dfs(level, position):
    global cnt

    if level == len(code):
        tmp = []
        for x in range(position):
            if ret[x] in alpha_dict:
                tmp.append(alpha_dict[ret[x]])
        print("".join(tmp))
        cnt += 1
    else:
        for i in range(1, len(alpha_dict)+1):
            try:
                if code[level] == i:  # 1~26까지 숫자 중 한자리 숫자인가?
                    ret[position] = i
                    dfs(level+1, position+1)
                # i가 한자리일때도 불필요한 탐색을 하지 않기 위해 i >= 10
                elif i >= 10 and code[level] == i // 10 and code[level+1] == i % 10:
                    ret[position] = i
                    dfs(level+2, position+1)
            # 마지막 자릿수 탐색시 1~26까지의 숫자면 elif 조건절에 걸려서
            # 다음 인덱스까지 참조하기 때문에 예외처리
            except IndexError:
                pass


dfs(0, 0)
print(cnt)