프로그래머스 84512 - 모음사전 (Lv.5)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/84512

// 프로그래머스 84512 - 모음사전 (Lv.5)
// https://school.programmers.co.kr/learn/courses/30/lessons/84512

// 문제 설명
// A, E, I, O, U 다섯 글자만으로 만들 수 있는 길이 1~5의 모든 단어를
// 사전순으로 나열한 사전이 있다. 주어진 단어 word가 몇 번째인지 반환하라.

// 제약 조건
// 1 <= word 길이 <= 5
// word는 A, E, I, O, U 로만 구성

// Example
// Input : "AAAAE" -> Output: 6
// Input : "AAAE"  -> Output: 10
// Input : "I"     -> Output: 1563
// Input : "EIO"   -> Output: 1189

// 접근 — 사전 자체를 사전순 DFS로 재현하고 순번을 세기
// "몇 번째냐"를 수식으로 풀 수도 있지만, 사전순 = A,E,I,O,U 순 DFS 방문순서와 정확히 같다.
// 즉 사전을 실제로 만들면서 세면 순번 규칙을 따로 유도할 필요가 없다.
// 1) 빈 문자열에서 시작해 A,E,I,O,U 순으로 한 글자씩 붙여 내려간다.
// 2) 단어를 하나 만들 때마다 order를 1 올린다 — 이 값이 곧 그 단어의 사전 순번.
// 3) 길이 5에 도달하면 더 내려가지 않고 형제로 넘어간다.
// 전체 단어 수는 5 + 25 + 125 + 625 + 3125 = 3,905개로 고정이라 사실상 O(1).
// 시간 O(5^5), 공간 O(5) (재귀 깊이)

#include <string>

using namespace std;

string target;                                 // 찾는 단어
int order, answer;                             // 전역 0 초기화에 의존

void dfs(string cur) {
    if (cur == target) { answer = order; return; }   // 빈 문자열은 target(길이 >= 1)과 겹치지 않는다
    if (cur.size() == 5) return;                     // 길이 상한 — 여기서 가지를 닫는다

    for (char c : string("AEIOU")) {            // 사전순 = 이 순서
        order++;                                // 단어 하나 생성 = 순번 하나 소비
        dfs(cur + c);
    }
}

int solution(string word) {
    target = word;
    order = 0; answer = 0;
    dfs("");
    return answer;
}

정리

• 핵심 관찰은 하나다. 사전순 나열 = A,E,I,O,U 순 DFS의 방문 순서. 이 사전은 “짧은 단어 먼저”가 아니라 순수 사전순이라서 AAAA(4글자) 다음이 AAAB류가 아니라 더 긴 AAAAA다 — 접두사가 자신보다 앞에 오는 규칙이 곧 “부모를 방문한 뒤 자식으로 내려간다”는 전위 순회다. 실제 순서 A(1) → AA(2) → AAA(3) → AAAA(4) → AAAAA(5) → AAAAE(6) → … → AAAE(10)가 DFS 방문 순서와 그대로 일치한다.
• 이 관찰이 있으면 순번 공식을 유도하지 않아도 된다. 방문할 때마다 order++ 하고 목표와 같으면 그 값을 답으로 쓰면 끝. 5진수 자리 가중치((5^(5-i) - 1) / 4)를 세워 O(1)로 풀 수도 있지만, 전체 후보가 3,905개로 고정이라 완전탐색이 상수 시간과 다를 게 없다. 여기서 수식을 유도하는 건 검증할 게 늘어나는 손해다.
• 종료 조건 두 개의 순서가 정답을 가른다. cur == target 검사가 cur.size() == 5 검사보다 먼저 와야 길이 5인 단어(예: "UUUUU" → 3905)를 찾을 수 있다. 순서를 뒤집으면 5글자 목표는 판정 전에 return되어 답이 0으로 남는다. 완전탐색에서 “가지를 닫는 조건”과 “답을 확정하는 조건”이 같은 지점에 있을 때는 확정을 먼저 둔다.
• order++를 재귀 호출 직전에 두는 게 인덱싱의 요점이다. 루트(빈 문자열)는 사전에 없는 0번이고, 자식을 만드는 순간 순번을 1 올려 넘긴다 — 그래서 첫 단어 "A"가 자연히 1번이 된다. 만약 함수 진입부에서 올리면 루트가 1번을 먹어 전부 1씩 밀린다. 1-base 순번은 “몇 개 만들었나”를 세면 자동으로 맞는다.
• 문자 후보를 for (char c : string("AEIOU"))로 순회한 건 순회 순서를 코드에 그대로 드러내기 위한 것이다. 이 순서가 곧 사전순 정의라서 배열을 따로 선언하고 인덱스로 접근하면 “왜 이 순서인가”가 흐려진다. 문자열 순회로 인덱스 변환 없이 char를 바로 받는 방식(c - '0'류 습관과 같은 계열)이 의도를 짧게 표현한다.
• 답을 찾은 뒤에도 순회를 멈추지 않는데, 남은 노드가 최대 3,905개라 조기 종료 플래그를 추가할 이유가 없다. 탐색 공간이 상수로 묶여 있으면 가지치기 코드는 성능이 아니라 복잡도만 늘린다.
• 검증: 예제 4개(6, 10, 1563, 1189)와 경계 케이스("A" → 1, "UUUUU" → 3905 = 전체 단어 수) 통과 (MSVC /std:c++17 컴파일·실행). 커리큘럼 97번.

핵심 요약 — 사전순 나열은 A,E,I,O,U 순 DFS 방문 순서와 같으므로, 순번 공식을 유도하지 말고 사전을 만들면서 order++로 세면 된다. 단 cur == target 판정이 size() == 5 가지치기보다 먼저 와야 길이 5 단어를 놓치지 않고, order++를 재귀 호출 직전에 둬야 1-base 순번이 맞는다.