[프로그래머스] 모음사전 (DFS)

문제 소개

오늘은 모음 사전 - 프로그래머스 문제를 정리합니다.
이 문제는 모음만으로 구성된 모든 단어를 사전순으로 나열했을 때, 주어진 단어가 몇 번째인지 구하는 완전탐색 문제입니다.
문제의 핵심은 길이 제한(최대 5) 내에서 가능한 모든 조합을 사전 순서대로 탐색하면서 원하는 단어의 인덱스를 찾는 것입니다.

문제 링크: 모음 사전 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

 

1. 가능한 모든 단어를 DFS로 만들어가며 사전 순으로 탐색
2. 각 문자 위치마다 A → E → I → O → U 순서로 조합
3. DFS를 순회하며 단어가 일치할 경우 현재 순서를 반환

 

---

해결 과정 및 코드

핵심 아이디어

1. 문자열을 앞에서부터 하나씩 붙이면서 DFS 방식으로 단어 생성
2. A, E, I, O, U 순서로 조합하여 최대 5글자까지 생성
3. 문자열이 생성될 때마다 order 증가시키고, 목표 단어에 도달하면 종료

코드

시간 복잡도 :O(5⁵)
이유: 가능한 단어 수는 5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 3905로, 완전탐색으로 충분히 처리 가능

 

class Solution {
    static int order;
    static String[] ALPHA = {"A", "E", "I", "O", "U"};

    public int solution(String word) {
        order = 0; // 전역 변수 초기화
        findOrderDfs("", word); // DFS 시작
        return order;
    }

    private boolean findOrderDfs(String str, String word){
        // 현재 단어가 찾는 단어와 같다면 true 반환
        if (str.equals(word)) return true;
        
        // 길이 제한 (최대 5글자)
        if (str.length() == 5) return false;

        for (int i = 0; i < 5; i++) {
            order++; // 새로운 단어를 하나 더 생성했으므로 순서 증가
            if (findOrderDfs(str + ALPHA[i], word)) return true; // 찾으면 종료
        }

        return false; // 못 찾았을 경우
    }
}