(프로그래머스 연습 문제 풀이) 모음 사전

문제 설명
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

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

입출력 예
word          result
"AAAAE"        6
"AAAE"         10
"I"              1563
"EIO"          1189

입출력 예 설명
입출력 예 #1
사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다. "AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2
"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3
"I"는 1563번째 단어입니다.

입출력 예 #4
"EIO"는 1189번째 단어입니다.

# 블로그 참고 코드
def solution(word):
    char = {'A': 0, 'E': 1, 'I': 2, 'O': 3, 'U': 4}
    answer = len(word) # A를 0으로 두었기 때문에 길이로 초기화 필요
    re = (((5 + 1) * 5 + 1) * 5 + 1) * 5 + 1 # 781
    for i in word:
        answer += re * char[i] # 첫 문자가 무슨 글자로 시작하는지
        re = (re - 1) // 5
    return answer

해당 문제는 볼 때부터 코딩보단 규칙을 찾는 문제임을 알았다. 계속 써내려가다보면 규칙이 보이겠지 하며 노가다로 작성해보아도 도대체 규칙이 발견되지 않았다(내 머리 ㅠ) 결국 구글링을 해보고 블로그를 보고 힌트를 얻었다.

문제에서도 나와 있듯이 사전 순서는 A가 1이고, I는 1563이다. 이때 생각해볼 수 있는 것은 맨 앞의 글자가 바뀔 때 어떤 규칙이 있는가이다. A=1, E=?, I=1563 이렇게 보면 A와 I 간의 차이는 1562이기 때문에 A와 E 간의 차이는 아마 그 절반인 781이 아닐까 추측해볼 수 있다.

아니면 직접 글자를 써가며 규칙을 찾을 수도 있다. 이때 글자보단 A=1, E=2, I=3, O=4, U=5 처럼 숫자로 치환하고 비교하면 직관적이다.

1
11
111
1111 + 1
11111 - 1번
11112 - 2번
11113 - 3번
11114 - 4번
11115 - 5번
1112 + 1
11121 - 1번
...

위의 예시를 살펴보면 각 자릿수가 바뀌는 규칙은 (x 5) + 1 이다. 이를 각 자릿수에 적용하면 단어 수가 총 5개이므로 4개까지 반복하면 된다(781에 해당).

위 코드에서 answer = len(word) 로 초기화한 이유는 딕셔너리 char에서 A를 0으로 두었기 때문이다. 하지만 AAAAA=5이므로 길이로 초기값을 정한 것이다.

---

아래는 모범 참고 코드를 가져온 것인데, 어차피 문자열이 5개밖에 없기 때문에 product 메서드를 통해 가능한 경우의 수를 모두 구했다.

# 모범 참고 코드
from itertools import product

solution = lambda word: sorted(["".join(c) for i in range(5) for c in product("AEIOU", repeat=i+1)]).index(word) + 1

참조
[프로그래머스/python] 위클리 챌린지 5주차 : 모음 사전 (tistory.com)