[Programmers] 모음 사전

문제

사전에 알파벳 모음 '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번째 단어입니다.

---

풀이

풀이1 (itertools 중복 순열 사용)

처음 문제를 접했을 때는 어떻게 풀어야 할지도 모르겠어서 냅다 다 만든 다음에

정렬하고 list의 index를 이용해서 순서를 찾았다.

from itertools import product

def solution(word):
    lst = []
    arr = ['A', 'E', 'I', 'O', 'U']
    for i in range(1, 6):
        for j in list(product(arr, repeat=i)):
            lst.append(''.join(j))
    
    lst.sort()
        
    return lst.index(word)+1

 

풀이2 (재귀 사용)

다른 사람이 재귀를 어떻게 사용했는지 풀이를 보고 다음날 다시 복기하면서 풀어보았다.

처음 재귀를 사용하려고 생각했을 때는 입력값에서 하나씩 바꿔나가는 방식으로 재귀를 사용해야지 했는데

그게 아니라 아무것도 없는 상태에서 하나씩 바꿔가면서 순서를 찾아야 한다.

def solution(word):
    answer = 0
    new= ''
    
    def sol(w):
        nonlocal answer
        answer += 1

        if w == word:
            return True
        elif len(w) == 5:
            return False

        for a in 'AEIOU':
            if sol(w+a) == True:
                return True
    
    for a in 'AEIOU':
        if sol(new+a) == True:
            return answer

 

두 풀이 방법의 속도 차이를 확인해보았다.

왼쪽이 리스트 인덱스 사용, 오른쪽이 재귀

 

재귀로 푼 방법이 훨씬 단축되는 것을 알 수 있다.

 

그리고 재귀함수를 만들면서 원래는 본래 함수 밖에 재귀함수를 만들고 global로 전역변수를 바꾸도록 하는데

이번에는 본래 함수 내부에 재귀함수를 만들고 nonlocal로 지역 변수를 비지역변수로 바꾸는 방법을 사용해보았다.