프로그래머스 Level 2 | 모음 사전 | Python 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/84512

---

문제 파악

조금 특별한 사전이 있다고 한다.

이 사전에는 알파멧 모음 'A','E','I','O','U' 으로만 적혀있고, 사전순으로 정렬되어있다고 한다.

첫번째 단어는 'A' 이고, 그다음은 'AA', ... 마지막 단어는 'UUUUU
라고 한다.

어떤 문자열 word를 주었을때, 그 word가 이 특별한 사전에 몇번째에 수록되어있는 지 return하는 문제이다.

A
AA
AAA
AAAA
AAAAA

AAAAE 6번째
AAAAI
AAAAO
AAAAU
AAAE 10번째

AAAEA
AAAEE
AAAEI
AAAEO
AAAEU
AAAIA
.
.
.
뭐 이런식으로 진행 되나보다.

어떻게 풀 수 있을까?

---

이는 앞자리가 바뀔때마다, 뒤에 올 수 있는 모든 조합을 한번에 건너뛰는 개수를 미리 알면 된다.
[781,156,31,6,1]

무슨 말이냐면

1. 마지막 자리가 바뀔때
   AAAA, 마지막 글자 A -> E
   이는 그냥 1개씩 증가한다.

2. 끝에서 두번째 자리가 바뀔때

AAA, 네번째 글자 A->E

2-1. AAAA 네개로 그냥 끝나는 경우. 1개
2-2 뒤에 한글자가 더 붙는 경우, 5개
AAAA A
AAAA E
AAAA I
AAAA O
AAAA U

합계 1+5 = 6개

즉 'AAAA' 6개가 지나가고 나서 'AAAE' 가 온다.

3. 끝에서 세번째 자리가 바뀔때

AAA -> AAE

1. 그자리에서 끝나는 경우 , 1개
   AAE

2. 뒤에 한글자가 붙는 경우 , 5개
   AAE A
   AAE E
   AAE I
   AAE O
   AAE U

3. 뒤에 두글자가 붙는 경우, 5x5 = 25개
   AAE AA
   AAE AE
   AAE AI
   .
   .
   AAE UU

1+5+25 = 31

4. 끝에서 네번쨰 자리가 바뀔떄는 위 과정과 같기에 유추해보면
   1+5+25+125 = 156이 된다.

5. 맨 앞자리가 바뀌는 경우도 마찬가지로
   1+5+25+125+625 = 781이 된다.

그래서 이 ㅈ

해답 및 풀이

def solution(word):
    vowels = {'A':0, 'E':1, 'I':2, 'O':3, 'U':4}
    weights = [781, 156, 31, 6, 1]  # 자리별 가중치

    ans = 0
    for i in range(len(word)):         # 0, 1, 2, ...
        ch = word[i]                   # 현재 자리의 문자
        ans += vowels[ch] * weights[i] # 그 자리 건너뛰는 블록 수 더하기
    ans += len(word)                   # 건너 뛰는 경우말고 본인 스스로도 더해줘야하기에.
    return ans

예시: "EIO" / len("EIO") = 3
i=0, ch='E' → 1 781 = 781
i=1, ch='I' → 2 156 = 312
i=2, ch='O' → 3 * 31 = 93
길이 3 더하기 → +3

ans = 1189

왜 ans 에 len(word) 도 더해주냐면
위 ans += voewl[ch] * weights[i] 는 건너뛰는 겅우의수만 구해준 것이다.

그래서 A 의 경우 첫번째 단어고 1을 return 해줘야 하는데

ans += voewl[ch] * weights[i] 만 해주면 weights[0] = 0이 되어
ans = 0가 된다.

그래서 len(word)까지 해줘야 정확한 계산이 된다.