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

문제

• 사전에 알파벳 모음으로 만들 수 있는 길이 5 이하의 단어가 수록되어 있다. 첫 단어는 A 이고, 그 다음은 AA 이고, 마지막 단어는 UUUUU 이다.
• 단어 word 가 주어질 때 이 단어가 사전에서 몇 번째 단어인지 리턴하기

 

풀이 1

• 전체 단어 리스트 중 현재 단어의 위치 찾기
  • product 사용해 전체 단어 리스트를 만든다.
  • bisect_right 이용해 현재 단어가 몇 번째 단어인지 찾는다.
• 시간 복잡도 : 단어의 길이가 최대 5 이므로, 전체 단어의 개수는 3905개가 된다. 

 

from itertools import product
from bisect import bisect_right

def solution(word):
    vowels = ['A', 'E', 'I', 'O', 'U']  # 모음
    words = ['A', 'E', 'I', 'O', 'U']   # 전체 단어 리스트
    
    for i in range(2, 6):   # 단어의 길이별로 단어 생성
        for w in product(vowels, repeat=i) :
            words.append(''.join(w))
    words.sort()    # 정렬
    return bisect_right(words, word)    # 단어 위치 찾기

 

풀이 2

• 단어의 각 알파벳을 보고 단어 개수 세기
• 단어의 i 번째 위치에서 알파벳에 해당하는 단어의 개수를 확인한다.
• a[N] : 길이가 0~N 인 문자열의 개수
  • a[1] = 5 + 1 = 6
  • a[2] = 5 * 6 + 1 = 31
  • a[3] = 5 * 5 * 6 + 5 + 1 = 156
  • a[4] = 5 * 5 * 5 * 6 + 5 * 6 + 1 = 781
  • a[5] = 5 * 5 * 5 * 5 * 6 + 5 * 5 * 6 + 5 + 1 = 3906
• 따라서 a[N] = 5 * (a[N-1]-1) + 1 이 되므로 수열의 일반항을 구하면 다음과 같다,
  • a[N] = ( 5**N - 1) / 4
• EIO 의 경우
  • i = 0 : E 이므로 하나의 앞선 알파벳이 있고, A로 시작하는 단어의 개수는 총 781 개다.
  • i = 1 : I 이므로 2개의 앞선 알파벳이 있고, EA 또는 EE 로 시작하는 단어의 개수는 312개다.
  • i = 2 : O 이므로 3개의 앞선 알파벳이 있고 EIA 또는 EIE 또는 EII 로 시작하는 단어의 개수는 93개 이다.

 

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

 

 

 

References

• 프로그래머스 고득점Kit 완전탐색