프로그래머스 - 모음사전 / Level 2 / Python

문제 📋

프로그래머스 - 모음사전

풀이 📝

from collections import defaultdict


def dfs(txt):
    alphabets = ['A', 'E', 'I', 'O', 'U']
    answer.append(txt)

    for alphabet in alphabets:
        new_txt = txt + alphabet

        if len(new_txt) > 5:
            return

        if not visited[new_txt]:
            visited[new_txt] = True
            dfs(new_txt)


def solution(word):
    global answer
    global visited
    visited = defaultdict(bool)
    answer = []
    dfs("")

    return answer.index(word)

1. 문제 정의
   단어들을 문제의 조건에 따라 순서대로 쭉 나열했을 때
   특정 단어의 index를 반환하는 문제이다.

2. 시간 복잡도 계산
   완전 탐색이 먼저 가능한지 계산해 봤다.
   전체 경우의 수는 6^5 이므로 충분히 가능하다.

3. 문제 풀이
   이 문제의 key point는 주어진 조건에 따라 정확하게 단어들을 나열하는 것이다.
   근데 가만히 생각해보면 아무것도 없을 때를 루트 노드라고 가정하고
   'A', 'E', 'I', 'O', 'U'를 각각 자식 노드라고 생각하면
   depth 5인 트리 형태가 되는 것을 알 수 있다.

   그렇게 생각하면 문제에 나오는 단어의 생성 순서는
   Preorder traversal 즉, DFS 탐색 순서와 동일하다.

   따라서 DFS 순회를 하면서 노드들을 answer에 넣어줬고
   쉽게 word의 index를 구할 수 있었다.

4. 예외 사항
   기타 특이사항 없음.