모음 사전

• 무식한 방법은 모든 단어를 다 만들어 놓고서 그 중에서 word의 위치를 찾는 것이다. 단어의 갯수는 5^5 개밖에 안되므로, 단어를 전부 생성하고, word 를 찾는것 모두 O(5*5^5)으로 처리된다.
• 제대로 된 풀이는, 길이 n이하의 단어의 갯수, count[n]을 수식으로 계산해두는 것이다. 그 뒤, word의 첫글자가 'I'라면, 'A'또는 'E'로 시작하는 단어들은 모두 word보다 앞에 있다는 것을 알수 있다. 'A' 또는 'E'로 시작하는 단어의 갯수는 2 * count[4]이다. 마찬가지로 word의 두번째 글자가 'E'라면, 'IA'로 시작하는 단어들은 모두 word보다 앞에 있다. 이러한 단어의 갯수는 count[3]이다. 이런식으로 word보다 앞에 올수 있는 모든 단어의 갯수를 O(|word|)에 계산할수 있다.
• count[n]은 5^0 + 5^1 + … + 5^n 이다. 코드에서는 이 식대로 계산해서 코드를 만들었지만, 등비수열의 합 공식인 (5^n - 1)/(5-1)을 적용해서 쓰면 아래처럼 한줄에 코딩하는 것도 가능하다

  • def solution(word):
        return sum(1 + 'AEIOU'.index(ch) * (5**(5 - i) - 1) // 4 for i, ch in enumerate(word))

"""Solution code for "Programmers 84512. 모음 사전".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/84512
- Solution link: http://www.teferi.net/ps/problems/programmers/84512
"""


import bisect
import itertools

def solution(word):
    dic = []
    for i in range(1, 6):
        dic.extend(itertools.product('AEIOU', repeat=i))
    return bisect.bisect(sorted(dic), tuple(word))

"""Solution code for "Programmers 84512. 모음 사전".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/84512
- Solution link: http://www.teferi.net/ps/problems/programmers/84512
"""


def solution(word):
    v = 0
    count = [v := v + 5**i for i in range(5)]
    pos = sum(1 + 'AEIOU'.index(ch) * c for ch, c in zip(word, reversed(count)))
    return pos