프로그래머스(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)
코딩테스트 연습 - 모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이
seongho96.tistory.com
위 게시물의 설명에 따르면
마지막 자리면 문자가 바뀔 때마다 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