[알고리즘] 프로그래머스 - 모음사전 - 84512 파이썬 문제 풀이

문제 링크

문제

입출력 예시

조건

조건을 보게 되면 모든 경우를 다 따지더라도 6^5-1이다. 그러므로 무식하게 사전을 구현해서 풀어도 된다.

풀이 - 완전탐색

from itertools import combinations
def dictionaryCreater():
    arr = ["A","E","I","O","U"] * 5
    table = set()
    for i in range(1, 6):
        for j in combinations(arr, i):
            table.add(''.join(j))
    return sorted(list(table))

def solution(word):
    return dictionaryCreater().index(word) + 1

그냥 조합을 이용해서 모든 경우를 다 구해서 정렬해주는 dictionaryCreater라는 함수를 만들었다 ㅎㅎ 시간복잡도가 여유롭기 때문에 가능한 풀이법이다.

풀이 - 등비수열의 합

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

역시 똑똑한 사람이 많다. 인덱스와 함께 몇번째 자리에 어떠한 알파벳이 있는지를 반복으로 계산해서 답을 구하는 풀이방법인데 등비수열의 합을 이용했다고 한다. 만약 이런 비슷한 문제가 제한 시간이 매우 빡빡하게 나왔다면 이런 풀이법을 떠올려야하는데 쉽지 않은 것 같다. 확실히 사전을 구현한 풀이법보다 소요시간이 압도적으로 빠르다. 수학공부도 조금씩 해야겠다... 이런 식을 구하는 건 연습해두면 완탐뿐 아니라 DP라던지 재귀로 푸는 문제라던지 여러 곳에서 도움이 많이 될 것 같다.