프로그래머스 Lv.2 | Python | 모음사전

1. 문제 정보

프로그래머스

• 난이도: Lv.2

---

2. 문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

 

제한 조건

• word의 길이는 1 이상 5 이하입니다.
• word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다

---

3. 접근 기준

이 문제는 단순 계산 문제가 아니라, 모든 가능한 문자열을 사전 순으로 생성하는 문제다.

따라서 다음 기준으로 접근해야 한다.

• 가능한 모든 문자열을 만든다 (최대 길이 5)
• 생성 순서를 그대로 카운트한다
• 목표 단어가 나오면 그 시점의 순서를 반환한다

DFS로 문자열을 생성하면서 순서를 카운트하는 문제다.

---

4. 사용한 패턴 / 알고리즘

DFS (깊이 우선 탐색)

• 빈 문자열에서 시작
• 모음을 하나씩 붙여가며 문자열 생성
• 길이 5까지 확장

---

5. 핵심 아이디어

핵심은 사전 순으로 문자열을 직접 만들어가면서 순서를 세는 것이다.

• 현재 문자열 w가 목표 단어라면 탐색 종료
• 그렇지 않으면 모음을 하나씩 붙여 다음 문자열 생성
• 문자열을 하나 만들 때마다 answer를 증가

중요한 점은:

• DFS 호출 전에 answer += 1을 해줘야 생성되는 순서를 정확히 반영할 수 있다.

---

6. 풀이 코드

def solution(word):
    answer = 0
    vowels = ['A', 'E', 'I', 'O', 'U']

    def dfs(w, depth):
        nonlocal answer

        # 현재 문자열이 목표 단어면 종료
        if w == word:
            return True

        for v in vowels:
            if depth < 5:
                answer += 1  # 새로운 단어가 생성되는 순간 카운트 증가
                
                # 다음 문자열 생성
                if dfs(w + v, depth + 1):
                    return True  # 목표 단어 찾으면 즉시 종료

    dfs('', 0)
    return answer

---

7. 동작 흐름 예시

예: word = "EIO"

사전 생성 흐름 일부:

A
AA
AAA ...
E
EA
EAA ...
EI
EIA ...
EIO ← 여기서 종료

이처럼 DFS로 문자열을 생성하면서, 목표 단어가 나오는 순간까지 카운트를 증가시킨다.

---

8. 핵심 로직 요약

이 문제의 핵심은 모든 문자열을 사전 순으로 생성하면서 순서를 카운트하는 것이다.

• 빈 문자열에서 DFS 시작
• 모음을 하나씩 붙이며 문자열 생성
• 문자열이 생성될 때마다 카운트 증가
• 목표 단어가 나오면 탐색 종료

“DFS 문자열 생성 + 생성 순서 카운트 + 목표 도달 시 종료”

---

9. 정리

이 문제는 완전탐색처럼 보이지만, 실제로는 DFS로 문자열을 생성하는 구조를 이해하는 것이 중요하다.

• 사전 순 → DFS 탐색 순서와 동일
• 문자열 생성 → 트리 구조로 생각
• 종료 조건 → 목표 단어 발견