[프로그래머스] 모음사전

 

문제 설명

 

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

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

 

제한사항

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

---

풀이

모음으로 이루어진 길이 5 이하의 단어 중 주어진 단어의 순서를 탐색하면 된다.

알파벳은 중복 가능하며 단어의 순서는 A부터 시작한다

 

처음에는 순열을 사용하여 탐색할까 생각했지만,

 

A

AA

AAA

AAAA

AAAAA

AAAAE

AAAAI

.

.

UUUUU

 

순으로 탐색되기에 dfs를 사용하면 되겠다

answer = 0
cnt = 0
alphas = ['A','E','I','O','U']

def dfs(current, word):
    global cnt
    if current == word:
        global answer
        answer = cnt
    if len(current)==5:
        return
    for ch in alphas:
        cnt += 1
        dfs(current+ch, word)
   
def solution(word):
    dfs('', word)
    return answer

 

dfs의 동작 방식을 이해하고 있는지 확인하기 좋은 문제였다