알고리즘
프로그래머스[Python] - 모음사전
BKM
2024. 4. 15. 16:11
문제
https://school.programmers.co.kr/learn/courses/30/lessons/84512
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
풀이
나의 풀이
def solution(word):
answer = 0
lst = []
for i in ['A','E','I','O','U']:
tmp = [i]
while tmp:
letter = tmp.pop()
if len(letter)>=5:
lst.append(letter)
continue
else:
lst.append(letter)
for j in ['A','E','I','O','U','']:
if j=='':
continue
tmp.append(letter+j)
dic = {v:i for i,v in enumerate(sorted(list(set(lst))))}
answer=dic[word]+1
return answer
모든 조합을 구한 뒤에, 찾고자 하는 단어의 인덱스를 찾는 방식으로 진행했다.
다른 풀이
문제에서 설명된 순서에 따르면, 각 문자열의 조합은 다음과 같이 정리할 수 있다. 여기서 1을 빼주는 경우는 중복되는 조합을 제거하기 위함이다.
- AAAE : (A~AAAAA)+(AAAA+)+1 = 5+(5-1)+1 = 10
- AAE : (A~AAAAA)+(AAAA+)+(AAA+)+1 = 5+(5-1)+(5^2-1)+1 = 34
- AE : (A~AAAAA)+(AAAA+)+(AAA+)+(AA+)+1 = 5+(5-1)+(5^2-1)+(5^3-1)+1 = 158
따라서, 첫번째 모음의 경우에는 모음의 인덱스 i에 따라 {5+(5-1)+(5^2-1)+(5^3-1)+(5^4-1)}*i+1의 값을 가지게 된다.
이를 다시 정리하면, $(1+5+5^2+5^3+5^4)*i+1$로 정리할 수 있으며, 이는 등비수열의 합이기 때문에 공식에 의해,
$\frac{5^4-1}{5-1}*i+1$로 정리할 수 있다.
즉, A~U는 다음과 같은 규칙에 따라 계산된다.
- $A = \frac{5^4-1}{5-1}*0+1 = 1$
- $E = \frac{5^4-1}{5-1}*1+1 = 782$
- $I = \frac{5^4-1}{5-1}*2+1 = 1563$
- ...
같은 원리로, 두번째 모음의 경우에는 모음의 인덱스 i에 따라 $\frac{5^3-1}{5-1}*i+1$의 값을 가지게 되며, 세번째~다섯번째도 같은 원리로 계산된다.
따라서 이를 일반화하면, 모음의 인덱스 i에 따라
- 첫번째 모음 : $\frac{5^4-1}{5-1}*i+1$
- 두번째 모음 : $\frac{5^3-1}{5-1}*i+1$
- 세번째 모음 : $\frac{5^2-1}{5-1}*i+1$
- 네번째 모음 : $\frac{5^1-1}{5-1}*i+1$
- 다섯번째 모음 : $i+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