[programmers] 기능개발

문제 설명

사전에 알파벳 모음 ‘A’, ‘E’, ‘I’, ‘O’, ‘U’만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 “A”이고, 그다음은 “AA”이며, 마지막 단어는 “UUUUU”입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

아이디어

처음에 이 문제를 보자마자 backtracking으로 풀려고 생각했다.(오늘 마침 유튜브로 backtrackin 영상을 봤다 ㅋㅋ)
그런 생각으로 접근을 했더니..
55555 = 3125 가 나왔고
이말은 “UUUUU”가 3125가 나오면 되는거다.
근데 나는 여기서 계산을 잘못했었다.
내가 고려한거는
“AAAAA” ~ “UUUUU” 까지를 고려했다.
알파벳이 5개로 꽉 채워저 있는 경우만을 고려했다. (시간을 여기서 많이 허비했다.)

다시 생각을 하기 시작했고, 최종적으로 아래와 같은 방법으로 문제를 해결했다.

첫번째 = 1
두번째 = 25
세번째 = 125
네번째 = 625
다섯번째 = 3125

합치면 3905

5 25 125 625 3125

Example

“AAAAE”는
A는 어떤 자리에서든지 +1만 해주면 된다 1+1+1+1
E는 5번째 자리니깐 5 * 0
4 + 0 + 2 = 6
4는 A의 갯수
0은 E가 4번째 자리에 대한 가중치
2은 E가 가지는 고유번호

“EIO”는
625*1 + 125*1 + 25*1 + 5*1 = E가 1번째 자리에 대한 가중치
125*2 + 25*2 + 5*2 = I가 2번째 자리에 대한 가중치
25*3 + 5*3 = O가 3번째 자리에 대한 가중치
780 + 310 + 90 = 1180
1180 + 2 + 3 + 4 = 1189
2은 E가 가지는 고유번호
3는 I가 가지는 고유번호
4는 O가 가지는 고유번호

“I”는
625*2 + 125*2 + 25*2 + 5*2 = 1560
1560 + 3 = 1563
1560은 I가 1번째 자리에 대한 가중치
3는 I가 가지는 고유번호

code

def solution(word):
    answer = 0
    vowels = {"E": 1, "I": 2, "O": 3, "U": 4}

    for i in range(len(word)):
        if word[i] == "A":
            answer += 1
        else:
            for j in range(4, i, -1):
                answer += (5 ** (j - i)) * vowels[word[i]]
                print(answer)
            answer += vowels[word[i]] + 1

    return answer