출처
https://school.programmers.co.kr/learn/courses/30/lessons/84512
문제
모음으로만 이루어진 사전에서 몇번째인지 찾는 문제이다. 사실 왜 완전탐색인지는 잘 모르겠다.
접근 방법
파이썬 dict나 다른 문법에 익숙치 않아서 수학적인 방법밖에 생각나지 않았다.
한 자리에 5가지의 경우가 있으므로 5진수 개념을 사용해보려고 하였다.
여러가지 케이스를 아래와 같이 두고 구해보려고 하였다.
A => 1
AA => 2
AAA => 3
AAAA => 4
AAAAA =>5
AAAAE => 6
AAAE => 10
AAE => 34
그냥 단순히 5^4, 5^3, 5^2, 5^1, 5^0에 각각 인덱스를 곱해서 구할 수 있을까? 라는 발상에서 출발하여 대입해보니 맞지 않았다.
AAAAA를 보면, A는 각 자리에 관계없이 +1만 해주는 것을 알 수 있다.
AAAE(10)를 그 다음 살펴보자. AAA(3)와는 7 차이난다. 그리고 AAAA와는 6 차이가 나는 것을 알 수 있다.그렇다면 E가 가지는 가중치는 (5^0 + 5^1) * 1 이고, 그곳에 A가 기본적으로 가지는 가중치인 1을 더해주면 10이 된다.
이런 매커니즘을 통해 풀이하였다.
풀이
다시 한번 정리해보자면, 각 자리가 가지는 가중치를 구할 수 있는데, I의 경우 5^4의 자리에 위치 해있고, 그렇기 때문에 (5^4 + 5^3+ 5^2 + 5^1 + 5^0)에 인덱스인 2를 곱하고 A의 값인 1을 더해준 값을 가진다.
(5^4 + 5^3+ 5^2 + 5^1 + 5^0) * index + 1 = 1563
맨 앞자리 부터 가중치를 구해서 더하면 정답이 나온다.
def solution(word):
answer = 0
arr = ['A', 'E', 'I', 'O', 'U']
for i in range(len(word)):
tmp = 0
for j in range(0, 5-i):
tmp += (5 ** j)
answer += tmp*arr.index(word[i]) + 1
return answer