💻코딩테스트 문제 풀이4

Chapter5. 재귀

[문제18] 모음사전 - Level2

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

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

- word의 길이는 1 이상 5 이하입니다.

- word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

• 1. 재귀 함수를 정의

def find(data, p, step):
	if step == 6: return
    if p ! = '': data.append(p)
    for c in ['A', 'E', 'I', 'O', 'U']:
    	find(data, ''.join([p, c]), step + 1)

• 2. 함수를 실행하여 사전 만들기

data = []
find(data, '', 0)

• 3. 만들어진 사전에서 주어진 단어가 어디에 있는지 전체 탐색으로 찾기

for i in range(len(data)):
	if data[i] == word:
    	answer = i + 1
        break

[정답1]

def find(data, p, step):
	if step == 6: return
    if p ! = '': data.append(p)
    for c in ['A', 'E', 'I', 'O', 'U']:
    	find(data, ''.join([p, c]), step + 1)
        
def solution(word):
	answer = 0
    data = []
	find(data, '', 0)
    for i in range(len(data)):
		if data[i] == word:
    		answer = i + 1
        	break
            
return answer

[정답2_직접 계산]

def solution(word):
	preset = {
    	'A' : [1, 1, 1, 1, 1],
        'E' : [782, 157, 32, 7, 2],
        'I' : [1563, 313, 63, 13, 3],
        'O' : [2344, 469, 94, 19, 4],
        'U' : [3125, 625, 125, 25, 5]
	}
    
    answer = 0
    for idx, key in enumerate(word):
    	answer += preset[key][idx]
        
	return answer

[최종 정답3_등비수열의 합 이용]

def solution(word):
	answer = 0
    for i, n in enumerate(word):
    	answer += (5 ** (5 - i) - 1) / (5 - 1) * "AEIOU".index(n) + 1
	return answer