문제

문제설명

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

입출력 예 #3

"I"는 1563번째 단어입니다.

입출력 예 #4

"EIO"는 1189번째 단어입니다.

풀이

코드

def solution(word):
    wordN = {'A':0,'E':1,'I':2,'O':3,'U':4}
    word = list(word)
    org = 5**5
    answer = 0
    for i in word:
        answer += wordN[i]*(org-1)//4
        org //= 5
    answer += len(word)
    return answer

풀이

문제를 처음 봤을때는 규칙이 이해가 가지않았다.
그래서 그림을 그려 분석해보기로 했다.

먼저 5개의 글자가 다음과 같이 나무처럼 조합되는 모습을 상상했고 사전순대로 번호를 붙여보면

다음과 같이 번호가 부여된다고 알게되었다.
그러면 'A'가 1이라고 했을때 'E'는 어떻게 구할까?

바로 A를 포함 A에서 뻗어나오는 모든 노드의 개수를 세면 된다.
다행히 해당문제에서는 글자를 A E I O U의 다섯개로 한정을 했기에 등비가 깊이가 한칸씩 내려갈수록 5배로 늘어나는 등비가 5인 등비수열로 생각할 수 있었다.

위의 파란 박스 내부의 노드의 개수 + 1(E 자기자신) 을 하면 'E'의 번호를 구할 수 있다.
따라서 'E'를 구하는 방법은 1 + 5 + 25 + 125 + 625 + 1(E 자기자신) = 782이다.

물론 이렇게 구하지 않고도 등비수열의 합 공식이 존재한다.
나는 코드에서 해당공식을 이용하였다.

위에서 'E'의 번호를 구해보았다. 그러면 'EE'의 번호는 무엇일까?

위의 파란 박스 내부의 노드의 개수 + 1(E 자기자신) 을 하면 'EE'의 번호를 구할 수 있다.

이런식으로 앞에서부터 알파벳을 확인해가며 파란 박스를 다 더하는 과정을 계속하면 word의 번호를 알 수 있다.

예시)'IOEA'의 번호 구하기

위의 파란 박스의 노드를 구해서 더하면 번호를 알 수 있다.

따라서 나는 딕셔너리 자료형을 통해 각 문자에 번호를 부여하여 일정 단계에서 더해야할 파란 박스가 몇개인지 구하기 쉽게 하였고

각 단계 에서의 파란 박스의 노드수를 구하기 위해 org를 5^5로 미리 지정하여 공식의 계산이 쉽게하였다.

그리고 각 글자를 가리키는 작은 파란박스는 결국 자기자신을 포함하여 문자열의 길이만큼의 개수가 나오므로 마지막에 answer에 더해주도록 했다.

후기

처음 볼때는 규칙이 쉽게 이해가 가지 않았지만 그림을 그려 풀어보니 정말 빨리 풀렸다.
나는 일반항을 도출하여 푸는 방식에 가까웠지만 다른사람의 풀이를 보니 그냥 사전 전체를 생성하여 검색하여 푸는 사람도 있었다.
확실히 word의 문자가 5개로 제한되고 길이도 5로 제한되어서 충분히 가능하다고 생각되었다.

재밌는 계산 문제였다.