문제 18 - 모음 사전 (Python)

프로그래머스

 

알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는 길이 5 이하의 모든 단어가 수록된 사전에서, 특정 단어가 몇 번째 위치에 있는지 찾는 문제입니다. 재귀를 통한 완전 탐색 방식과 수학적 규칙을 활용한 계산 방식 두 가지로 접근할 수 있습니다.

---

1.  나의 풀이

사전의 모든 단어를 생성할 때, '현재 단어에서 다음 단어를 계산'하는 방식 대신 '빈 문자열에서 시작하여 모음을 순서대로 붙여나가는' 깊이 우선 탐색(DFS) 방식을 사용했습니다. 이는 사전의 순서를 자동으로 보장하며 로직을 단순화합니다.

def find(data, p, step):
    # 종료 조건: 단어의 최대 길이는 5이므로 step이 6이 되면 중단
    if step == 6:
        return
    
    # 빈 문자열이 아닌 경우에만 사전에 단어 추가
    if p != '':
        data.append(p)
    
    # 모음 순서대로 문자열을 확장하며 재귀 호출 (사전 순서 보장)
    for c in ['A', 'E', 'I', 'O', 'U']:
        find(data, ''.join([p, c]), step + 1)

def solution(word):
    data = []
    # 빈 문자열에서 시작하여 사전 생성
    find(data, '', 0)
    
    # 리스트에서 목표 단어의 인덱스를 찾아 1을 더해 반환
    return data.index(word) + 1

---

2.  오늘 배운 점 및 복기 노트

'선언적 사고'로의 전환

모든 경우의 수를 사전 순서대로 일단 다 만드는 '선언적 사고'를 적용했습니다. 빈 문자열에서 시작하여 for 문을 통해 모음을 하나씩 붙여나가는 방식은 스택의 구조를 활용한 깊이 우선 탐색(DFS)이 됩니다. 이를 통해 복잡한 if/else 분기 없이도 시스템이 자동으로 A -> AA -> AAA -> AAAA -> AAAAA -> AAAAE 순으로 탐색하도록 유도할 수 있음을 배웠습니다.

 

Level 0: (빈 문자열 '')
          │
          ├── A (Level 1)
          │    ├── AA (Level 2)
          │    │    ├── AAA (Level 3)
          │    │    │    ├── AAAA (Level 4)
          │    │    │    │    ├── AAAAA (Level 5) -> 종료(Step 6)
          │    │    │    │    ├── AAAAE (Level 5)
          │    │    │    │    ├── AAAAI (Level 5)
          │    │    │    │    ├── AAAAO (Level 5)
          │    │    │    │    └── AAAAU (Level 5)
          │    │    │    │
          │    │    │    ├── AAAE (Level 4) ...
          │    │    │    └── AAAI (Level 4) ...
          │    │    │
          │    │    ├── AAE (Level 3) ...
          │    │    └── AAI (Level 3) ...
          │    │
          │    ├── AE (Level 2) ...
          │    └── AI (Level 2) ...
          │
          ├── E (Level 1)
          │    ├── EA (Level 2) ...
          │    └── EE (Level 2) ...
          │
          └── ... (I, O, U로 시작하는 가지들)

 

재귀 설계의 핵심: 상태 정의

재귀 함수의 인자에 무엇을 담느냐에 따라 로직의 명확성이 달라집니다. 현재까지 만들어진 문자열(p), 현재 문자열의 길이(step), 결과를 저장할 리스트(data)로 상태를 정의하니 점화식이 매우 단순해졌습니다. 규칙이 복잡할수록 직접 계산하려 하기보다 재귀가 조합을 생성하게 만드는 것이 훨씬 간결합니다.

 

'절차적 사고' 기반의 최초 풀이 복기

학습 초기에는 "현재 상태에서 다음 단어를 어떻게 만들 것인가"를 직접 계산하는 방식으로 접근했습니다. 아래는 당시 작성했던 코드입니다.

import sys

sys.setrecursionlimit(10 ** 6)

vowel = ["A", "E", "I", "O", "U"]

def aeiou(idx, chars, word):
    # 목표 단어와 일치하는 경우 현재 인덱스 반환
    if len(word) == len(chars) and "".join(chars) == word:
        return idx

    if not chars:
        return aeiou(idx + 1, ['A'], word)
    else:
        # 길이가 5 미만이면 'A'를 추가하여 깊게 탐색
        if len(chars) < 5:
            return aeiou(idx + 1, chars + ['A'], word)
        # 길이가 5에 도달하면 마지막 글자부터 변경하며 탐색
        else:
            for i in range(4, -1, -1):
                if chars[i] != "U":
                    return aeiou(idx + 1, chars[:i] + [vowel[vowel.index(chars[i]) + 1]], word)
            return None

def solution(word):
    return aeiou(0, [], word)

 

위 코드는 마지막 글자가 'U'인지 확인하고, 인덱스를 직접 넘겨주며, 다음 모음을 찾기 위해 다시 index()를 호출하는 등 매우 세밀한 규칙을 직접 제어해야 했습니다. 이로 인해 단어 길이가 변하는 규칙과 알파벳이 변하는 규칙을 동시에 처리하느라 조건문이 복잡해졌음을 확인했습니다.

 

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

수학적 통찰: 공백(Gap)의 크기 계산

재귀로 풀 수 있는 문제는 수학적 규칙으로도 해결 가능합니다. 첫 번째 글자가 'A'에서 'E'로 바뀔 때 발생하는 간격은 첫 자리가 'A'인 모든 경우의 수의 합과 같습니다.

1. 첫 글자가 'A'인 1글자 단어: 1개
2. 두 번째 자리가 결정되는 경우: \( 5^1 = 5 \)개
3. 세 번째 자리가 결정되는 경우: \( 5^2 = 25 \)개
4. 네 번째 자리가 결정되는 경우: \( 5^3 = 125 \)개
5. 다섯 번째 자리가 결정되는 경우: \( 5^4 = 625 \)개 이들을 합산하면 총 781개의 단어가 존재하며, 이는 등비수열의 합 공식인 \( \frac{5^n - 1}{5 - 1} \)로 일반화할 수 있습니다.

실행 전략의 선택 (Brute Force vs Math)

전체 경우의 수가 3,905개로 작을 때는 재귀를 통한 완전 탐색이 안전한 선택입니다. 하지만 단어의 최대 길이가 매우 커진다면 메모리 제한과 시간 복잡도 문제로 인해 반드시 수학적 계산 방식을 택해야 합니다. "하나의 선택이 뒤에 오는 몇 개의 선택지를 결정짓는가"를 고민하여 패턴을 찾는 능력이 대규모 데이터 처리에서 필수적임을 배웠습니다.

 

상태 전이의 이해와 코드 개선

절차적 사고 기반 최초 풀이처럼 '현재 상태에서 다음 상태를 찾는 방식'보다는 '처음부터 끝까지 가지를 뻗어나가는 방식'이 재귀의 본질에 더 가깝습니다. 복잡한 if 문들을 재귀의 인자와 for 문 하나로 녹여내는 연습이 실무와 테스트 모두에서 통용되는 깔끔한 코드의 시작임을 깨달았습니다.