모음사전

import sys sys.setrecursionlimit(10**7) def dfs(start, target, order): if start == target: return order alphabets = ['A', 'E', 'I', 'O', 'U'] if len(start) < 5: start += 'A' else: # 알파벳의 길이가 5인 경우 last_alphabet = start[-1] if last_alphabet != 'U': # 마지막 알파벳이 U가 아닌 경우 last_alpha_index = alphabets.index(last_alphabet) start = start[:-1] + alphabets[last_alpha_index+1] # 마지막 알파벳 레벨 증가 else: # 마지막 알파벳이 U인 경우 while last_alphabet == 'U': # 뒤에서부터 모든 U를 제거 start = start[:-1] last_alphabet = start[-1] last_alpha_index = alphabets.index(last_alphabet) start = start[:-1] + alphabets[last_alpha_index+1] # 마지막 알파벳 레벨 증가 result = dfs(start, target, order+1) return result def solution(word): ''' A -> AA -> AAA -> AAAA -> AAAAA | 알파벳 길이 < 5 AAAAA -> AAAAE -> AAAAI -> AAAAO -> AAAAU | 알파벳 길이 = 5 AAAAU -> AAAE | 마지막 알파벳 = U AAAE -> AAAEA | 알파벳 길이 < 5 AAAEA -> AAAEE AAAEI AAAEO AAAEU | 알파벳 길이 = 5 AAAEU -> AAAI | 마지막 알파벳 = U AAAI -> AAAIA | 알파벳 길이 < 5 AAAIA -> AAAIE AAAIO AAAIU | 알파벳 길이 = 5 AAAIU -> AAAO | 마지막 알파벳 = U AAAUU -> AAE ------------------------------------------------------------ 1. 알파벳 길이가 5보다 작을 때, 가장 뒤에 A를 추가 2. 알파벳 길이가 5인 순간, 가장 뒷 알파벳의 레벨을 1 증가 (ex. A -> E / E -> I) 3. 단, 맨 마지막 알파벳이 U일 때 - 3.1 알파벳 U를 모조리 삭제 - 3.2 마지막 알파벳의 레벨을 1 증가 (ex. A -> E / E -> I) ''' answer = dfs('A', word, 1) # start, target word, order return answer