[프로그래머스] 모음사전 (level2, python)

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

 

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

 

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

---

 

입출력 예

 

---

입출력 예 설명

 

입출력 예 #1

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

 

입출력 예 #2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

 

입출력 예 #3

"I"는 1563번째 단어입니다.

 

입출력 예 #4

"EIO"는 1189번째 단어입니다.

---

풀이 코드

def solution(word):
    letter = 'AEIOU'
    answer = 0
    count = 0
    
    def dfs(now, target):
        nonlocal count
        nonlocal answer
        
        if now == target:
            answer = count
            return

        if len(now) > 5:
            return

        count += 1

        for l in letter:
            dfs(now+l, target)
        
    dfs('', word)
    return answer

DFS를 통해 풀었다.

이 코드의 단점은, now == target인 것을 찾아서 리턴을 하더라도,

재귀적 함수의 특성상 재귀 스택에 쌓인 모든 것들이 리턴되진 않는다.

따라서 시간 복잡도 측면에서 손해를 보는 면이 있다.

 

itertools 모듈을 사용해 모든 조합을 만들어서 풀이하거나,

심지어 5중 for문을 사용해 풀이해도 풀린다.