프로그래머스(programmers) 모음사전 python 정답 [완전 탐색]

프로그래머스(programmers) 모음사전 python 정답 [완전 탐색]

문제 링크

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

문제 정답

입출력 예

word	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189

정답 코드

def solution(word):
    answer = 0
    for i, n in enumerate(word):
        answer += (5 ** (5 - i) - 1) / (5 - 1) * "AEIOU".index(n) + 1
    return answer

문제 해설

https://seongho96.tistory.com/50

[JAVA 풀이] 프로그래머스 - 모음사전 (Level 2)

위 게시물의 설명에 따르면

마지막 자리면 문자가 바뀔 때마다 1씩 증가하고, 4번째 자리인 경우는 6씩 증가하고, 3번째 자리인 경우는 31씩 증가하는 것을 볼 수 있다.

따라서 자릿수의 증가량은 등비수열의 합으로 계산할 수 있다.

AAAA에서 AAAE가 돠려면 AAAAA를 거쳐 AAAE가 되야 한다.

즉 5 + 1(변경 연산)의 횟수가 필요하다,

 

AAA에서 AAE가 되려면 AAAAA를 거쳐 AAAE가 되어야 하고,

AAAE를 거쳐 AAAO가 되어야 한다.

 

즉 5+1이 5번 있어야 한다. 5*5 +5 +1다.

1은 자리올림을 위해 필요하다

 

AA에서 AE는 5*5*5 + 5*5 +5 +1이 된다.

A에서 E는 이제  5*5*5*5 + 5*5*5 +5*5+5 +1 임을 알 수 있다.

 

이를 등비수열의 합을 이용한 점화식으로 바꿔 표현하면 정답 코드가 된다.

뒷 자리부터는 앞이 없는 것처럼 생각하고 계산할 수 있다.

def solution(word):
    answer = 0
    for i, n in enumerate(word):
        answer += (5 ** (5 - i) - 1) / (5 - 1) * "AEIOU".index(n) + 1
    return answer