위클리 챌린지 #7. 모음 사전

• 코딩테스트 연습 - 모음사전 | 프로그래머스 (programmers.co.kr)
• 모음 사전

문제 설명

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

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

제한사항

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

---

입출력 예wordresult

"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번째 단어입니다.

 

---

( 문제 해설 )

 

* 생각 알고리즘 흐름도 *

 

0. 이문제는 5개의 알파벳(a, e, i, o, u)가 조합된 단어가 주어졌을 때 조합된 단어를 사전 형식으로 순서를 정했다고 했을 때 사전 순서의 몇 번째인가를 묻는 질문이다.

 

0 - 1. 단어가 u가 되었을 때 앞에 단어를 a => e 이런식으로 카운팅 하는 방법은 시간 초과가 납니다.

0 - 2. 이문제는 단어 순서의 원리을 이용하여 문제를 풀 수 있습니다.

0 - 3. 단어가 총 몇개까지의 경우의 수를 가질 것 같나요? 

앞 자릿수부터 5^5, 5^4, 5^3, 5^2, 5^1 이렇게 될 거 같지 않나요? 왜 그렇냐고요?

_ _ _ _ _ <= 단어의 인덱스 있겠죠.

            _ <= 위치의 경우의 수는? a, e, i, o, u 총 5개

         _    <= 위치의 경우의 수는? 이전의 인덱스가 a, e, i, o, u를 거쳤을 때 해당 위치는 a => e가 되므로 총? 5^5 = 25개

..... 이런 식으로 계삽됩니다 결론적으로 5^5 + 5^4 + 5^2 + 5^1 = 3905개 되죠

1. 첫 번째 수는 3905 // 5를 계산한 값이 이 수가 가지고 있는 사전의 순서가 되는 겁니다.

2. 두 번째는 3905 // 25... 이런 식으로 마지막수까지

3. 그리고 a, e, i, o, u에 대해서 생각할 필요가 있습니다. a는 초기값입니다. 즉, aaaae라면 2번째 수죠?

그럼 a가 가지고 있는 값은? 0이어야겠죠. 하지만 그러면 aaaaa가 0이 돼버리니 +1을 해줍니다.

4. 다시 설명하면 altonum = {'A': 0, 'E': 1, 'I': 2, 'O': 3, 'U': 4} 이렇게 되는 것이고,

두 번째 수를 계산하는 거라면 두 번째 위치에 있는 알파벳이 e라면 e는 1이고 두 번째이므로 3905//25 = 156

156 * 1 번째 순서를 더하는 식으로 계산하는 것입니다.

5. 이를 코드로 구현하면 됩니다.

 

---

[코드] 

 

# 문자간의 길이 이용

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

    a = 3905 // 5
    b = 3905 // 25
    c = 3905 // 125
    d = 3905 // 625
    e = 3905 // 3125
    lang = [a, b, c, d, e]

    for i in range(len(word)):
        num = lang[i] * altonum[word[i]] + 1
        answer += num

    return answer

---

후기

 

사실 이문제는 수학적 계산을 통해 쉽게 풀었습니다.

혹시 누가 직접 구현으로 푸신분이 있다면 댓글 남겨주세요

배우고 싶네요

그럼 다들 즐공!!