모음사전

2026.04.20

문제 설명

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

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

제한 사항

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

입출력 예

문제 풀이

나의 코드

소요 시간: 55분

시간 복잡도: O($n^2$)

---

dfs() 내부에서 str += alpha[i], count++를 실행하는 바람에 dfs() 로직이 두번째 순회부터 꼬이는 일이 발생하였다.
dfs에 대해 더 익숙해지는 연습이 필요한 것 같다.

---

import java.util.Map;
import java.util.HashMap;

class Solution {
    private String alpha[] = {"A", "E", "I", "O", "U"};
    private boolean[] visited = new boolean[alpha.length];
    private Map<Integer, String> map = new HashMap<>();
    private int answer = 0;
    private String word;
    private int index = 0;
    
    public int solution(String word) {
        this.word = word;
        dfs("", 0);
        
        return answer;
    }
    public void dfs(String str, int count) {
        for (int i = 0; i < alpha.length; i++) {
            if (count < 5 && !map.containsValue(str + alpha[i])) {
                map.put(index++, str + alpha[i]);
                if ((str + alpha[i]).equals(word)) {
                    answer = index;
                    return;
            }
                dfs(str + alpha[i], count + 1);
            }
        }
    }
}

AI 코드 1

시간 복잡도: O($n$)

---

dfs는 중복을 허용하지 않으므로 map을 사용할 필요가 없음

---

class Solution {
    private String[] alpha = {"A", "E", "I", "O", "U"};
    private int answer = 0;
    private int index = 0;
    private boolean found = false;

    public int solution(String word) {
        dfs("", 0, word);
        return answer;
    }

    public void dfs(String str, int count, String word) {
        if (str.equals(word)) {
            answer = index;
            found = true;
            return;
        }
        if (count == 5) return;

        for (int i = 0; i < 5; i++) {
            if (found) return;
            index++;
            dfs(str + alpha[i], count + 1, word);
        }
    }
}

AI 코드 2

시간 복잡도: O($1$)

---

1글자: 1개
2글자: 5개
3글자: 25개
4글자: 125개
5글자: 625개
→ 한 글자 선택 시 뒤에 오는 단어 수 = 1 + 5 + 25 + 125 + 625 = 781

위와 같은 수학적 규칙을 이용하여 해결함

---

class Solution {
    public int solution(String word) {
        int[] base = {781, 156, 31, 6, 1};
        // 각 자리에서 알파벳 하나 선택 시 건너뛰는 단어 수
        // 1자리: (5^0+5^1+5^2+5^3+5^4) = 781
        // 2자리: (5^0+5^1+5^2+5^3) = 156
        // ...
        String alpha = "AEIOU";
        int answer = 0;

        for (int i = 0; i < word.length(); i++) {
            int idx = alpha.indexOf(word.charAt(i));
            answer += idx * base[i] + 1; // 해당 알파벳까지 건너뛴 수 + 현재 단어
        }

        return answer;
    }
}