알고리즘

프로그래머스[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