프로그래머스 고득점 Kit - 모음사전

Problem

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

프로그래머스

• 사전에 알파벳 모음 A,E,I,O,U 만 사용해 만들 수 있는 길이 5 이하의 단어가 수록되어 있다
• 사전에서 첫 단어는 A 이다
• 사전에서 두 번째 단어는 AA 이다
• 사전에서 마지막 단어는 UUUUU 이다
• 단어가 주어질 때, 해당 단어가 사전에서 몇번째에 위치했는지 반환해라.

Input / Output Examples

word	result
"AAAAE"	6
"AAAE"	10
"I"	1563

 

사전에서 단어는 A,AA,AAA,AAAA,AAAAA,AAAAE,AAAAI,AAAAO,AAAAU,AAAE 순서로 들어있다.

따라 AAAAE는 6번째, AAAE는 10번째에 들어있다.

 

Solution

파이썬 itertools 에서 제공하는 중복 열인 product를 사용했다.

A,E,I,O,U에서 1~5개를 뽑아 한줄로 나열하고, 이를 정렬하면 단어 사전을 완성할 수 있다.

이제 단어 리스트를 순회하면서 해당 단어가 몇번째에 있는지 탐색하면 된다.
좀 더 효율적인 탐색을 원하면 이진탐색을 구현해도 될 것 같다.

 

Code

from itertools import product

def solution(word):
    _word = ['A','E','I','O','U']
    wordList = []
    for i in range(1,6):
        wordList.extend(product(_word, repeat=i))
    wordList.sort()
    for i in range(len(wordList)):
        if word == ''.join(wordList[i]):
            return i+1

 

Result

이유는 모르겠지만 생각보다 실행속도가 괜찮다.

만약 알파벳 모음이 아니라 알파벳 전체였다면 이렇게 풀면 안되었을 것 같다..