문제 링크

풀이 과정

• 본 문제는 코드 블록에 풀이 과정을 제시하였습니다.

전체 코드

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