[Python] 프로그래머스 모음사전 풀이

문제 확인

프로그래머스

나의 풀이

• 단어의 최대 길이가 5 이하라서, 가능한 모든 단어를 모아 미리 사전을 구성해도 시간 초과가 발생하지 않을 것이라고 판단했다.
  • 경우의 수 : $6^5 = 7776$
• 단어 사전을 구성하기 위해서 중복 순열 product를 이용했고, 중복을 방지하기 위해서 set 자료형을 활용했다.

# 길이 5 이하의 단어
# 중복 순열 만들어도 시간 초과 X
from itertools import product

def solution(word):
    word_dic = set()
    for p in product(["", "A", "E", "I", "O", "U"], repeat = 5):
        word_dic.add("".join(p))
    word_dic = sorted(word_dic)
    for idx, w in enumerate(word_dic):
        if w == word:
            return idx

다른 사람 풀이

DFS를 활용한 풀이

• 단어 사전을 구성하기 위해서 DFS를 활용했다.

order = 0    

def solution(word):
    answer = 0
    dic = {}
    lst =["A","E","I","O","U"]
    def dfs (s):
        global order
        if len(s) > 5:
            return
        dic[s] = order;
        order += 1
        for i in lst:
            if(len(s+i) > 5):
                return
            dfs(s + i)
    dfs("")
    return dic[word]

 

프로그래머스 위클리챌린지 5주차_모음사전 (dfs)

규칙을 활용한 풀이

• [781, 156, 31, 6, 1] : 'A-E', 'E-I' 처럼 순서가 1만 차이날 경우, 경우의 수를 계산한 것이다.
  • 1: 맨 뒷자리만 다른 경우
    • 1 = 1
  • 6 : 뒤에서 두번째 자리가 다른 경우 → 두번째 자리에서 1 차이나고(+1), 뒷 자리가 다른 경우 * 5
    • 5 * 1(나머지 자리) + 1(현재 자리) = 6
  • 31 : 뒤에서 3번째 자리가 다른 경우 → 세번째 자리에서 1 차이나고(+1), 나머지 자리가 다른 경우 * 5
    • 6 * 5(나머지 자리) + 1(현재 자리)  = 31 
  • 이를 재귀적으로 반복하면 나머지 성분도 구할 수 있다.
• [781, 156, 31, 6, 1]을 통해서 순서가 1만 차이날 경우를 계산해 뒀으니, 순서가 차이나는 만큼 곱해주면 최종적으로 원하는 순서를 얻을 수 있다.

def solution(word):
    answer = 0
    arr = ['A', 'E', 'I', 'O', 'U']
    num = [781, 156, 31, 6, 1]
    for i in range(len(word)):
        answer += arr.index(word[i]) * num[i] + 1
    return answer

 

프로그래머스 2단계 - 모음사전 (Python)