[프로그래머스/Lv.2] 모음사전 | 완전탐색 | 파이썬

문제

https://school.programmers.co.kr/learn/courses/30/lessons/84512

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

 

다른 사람의 풀이1

def solution(word):
    vowels = "AEIOU"
    words = []
    
    def dfs(cnt, w):
        if cnt == 5:
            return
        
        for i in range(5):
            words.append(w + vowels[i])
            dfs(cnt + 1, w + vowels[i])
    
    dfs(0, "")
    
    return words.index(word) + 1

빈 문자열에서 시작해 "A", "AA", "AAA", "AAAA" 순서로 더해 나가다가

만들 수 있는 단어의 최대 길이, 즉 `cnt == 5`인 경우 단어를 더하는 것을 종료한다.

 

이후에는 "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"...와 같이 

현재까지의 단어에 모음을 하나씩 추가하는 방식으로 새로운 단어를 만들면서 만들 수 있는 모든 단어를 차례대로 탐색한다.

 

만들어진 모든 단어 중에서 `word`의 인덱스를 검색해서 결과값을 반환한다.

 

다른 사람의 풀이2

from itertools import product

def solution(word):
    words = []
    
    for i in range(1, 6):
        for v in product(["A", "E", "I", "O", "U"], repeat=i):
            words.append("".join(v))
    
    words.sort()
    
    return words.index(word) + 1

`product`는 `itertools` 모듈의 함수로, 카르티시안 곱(Cartesian product)을 계산한다.

 

예를 들어, ["A", "E", "I", "O", "U"]에서 길이가 `i`인 모든 가능한 순서의 조합을 구한다.

`repeat=2`라면 ["A", "A"], ["A", "E"], ["A", "I"], ..., ["U", "U"]까지의 모든 조합이 생성되는 것이다.

 

이를 이용해 1~5를 길이로 가지는 단어의 모든 경우의 수를 리스트에 추가한 후

리스트를 사전순으로 정렬해서 인덱스를 통해 해당 단어의 사전의 위치를 구한다.