[인프런] 알파코드

---

문제설명

철수와 영희는 서로의 비밀편지를 암호화해서 서로 주고받기로 했다. 그래서 서로 어떻게 암호화를 할 것인지 논의하고 있다. 영희는 알파벳 A를 1로, B는 2로, ..., Z는 26으로 할당해서 번호를 보내기로 하자고 제안한다. 하지만 철수는 이에 반대한다. 왜냐하면 만약 BEAN을 보내서 암호화하면 25114 이다. 그러면 이를 다시 알파벳으로 복원할 때는 많은 방법이 존재한다고 한다. 즉, 25114를 분할하는 여러가지 방법을 생각해보자. 2/5/1/1/4, 2/5/1/14, 2/5/11/4 ,... 등등.. 

만약 호화된 코드가 주어지면 그것을 영희가 제안한 방법으로 알파벳으로 복원하는 데 얼마나 많은 방법이 있는지 구하라.

입력조건

• 첫줄에 숫자로 암호화된 코드가 입력된다. 단, 코드는 0으로 시작하지 않는다. 코드의 길이는 최대 50이다.

출력조건

• 입력된 코드를 알파벳으로 복원하는데 몇 가지의 방법이 있는지 각 경우를 출력한다. 마지막 줄에는 그 가지수를 출력한다. 단어의 출력은 사전순으로 출력한다.

사고과정

• 상태트리를 만들기 매우 힘들었다.. 갈래를 2갈래로 나누어서 특정 인덱스의 코드값을 포함시키냐 여부로 나누었는데.. 결국 실패했다..
• 풀이를 보니 역시 갈래길을 만드는 데서 내가 맞추지 못했다. 우선 상태트리의 레벨은 주어진 암호화된 코드의 인덱스를, 그리고 이를 담을 res 리스트의 인덱스로 두가지 인자를 갖는 DFS 함수를 정의한다.
• 그리고 난 후 어차피 1~26까지 숫자이기 떄문에 매 갈래길 마다 for loop로 1~26까지 돌면서 해당 숫자에 걸리면 DFS 탐색을 한다. 예를 들어, 주어진 코드가 25114 라면 처음에 1~26 루프를 돌다가 탐색가능한 경우는 2 랑 25이다. 이 때, 각각 또 DFS 탐색을 수행한다. 단, 자릿수가 1자리, 2자리 나오는 경우가 따로 있기 때문에 따로 처리해주어야 한다.
• 아이디어만 보고 스스로 구현하는 것에 성공했다. 그런데 1자리, 2자리 나오는 경우를 한번에 처리하는 조건이 매우까다로웠다.. 구현하긴 했지만..
• 풀이를 보니 자릿수가 하나, 두개일 때 따로 처리하도록 했다.. 그리고 code의 마지막 자리에 -1을 집어넣는 이유는 code의 마지막 숫자가 1 또는 2로 끝나게 되면 code[L+1] == i % 10 조건까지 가게되서 index out of range 에러가 발생하기 때문임도 기억하자!

풀이(스스로 못 푼 풀이)

- 강의 풀이

code = list(map(int, input().split()))
n = len(code)
code.insert(n, -1)  # code 마지막 값이 1또는 2이면 에러가발생하기 때문에 그 방지
res = [0] * (n+3)
cnt = 0


def DFS(L, P):
    global cnt
    if L == n:
        cnt += 1
        for j in range(P):
            print(chr(res[j]+ 64), end='')
        return
    else:
        for i in range(1, 27):
            # 자리개수 1개 일때
            if code[L] == i:
                res[P] = i
                DFS(L+1, P+1)
            # 자리개수가 2개 일때
            elif i >= 10 and code[L] == i//10 and code[L+1] == i % 10:
                res[P] = i
                DFS(L+2, P+1)


DFS(0, 0)
print(cnt)

- 나의 풀이

code = input()
n = len(code)
alpha = [chr(x) for x in range(ord('A'), ord('Z')+1)]
alpha.insert(0, 0)
res = [0] * n
answer = 0

def dfs(L, idx):
    global answer
    if L == n:
        result = ''
        for r in res:
            if r != 0:
                result += alpha[r]
        #print(result)
        answer += 1
        return
    else:
        for i in range(1, 27):
            str_i = str(i)
            if str_i == code[L:L+len(str_i)]:
                res[idx] = i
                dfs(L+len(str_i), idx+1)
                res[idx] = 0


dfs(L=0, idx=0)  # L은 code의 인덱스, idx는 res의 인덱스
print(answer)