모음사전_복습2

2026.09.27

문제 풀이

나의 코드

---

소요 시간: 21분
시간 복잡도: $O(1)$

---

class Solution {
    private String[] alpha = new String[]{"A", "E", "I", "O", "U"};
    private String word;
    private int cnt = 0;
    private boolean isFind = false;
    private void dfs(StringBuilder sb) {
        if (sb.toString().equals(word)) {
            isFind = true;
            return;
        }
        if (sb.length() >= 5) {
            return;
        }
        for (int i = 0; i < alpha.length; i++) {
            if (!isFind) {
                cnt++;
                dfs(sb.append(alpha[i]));
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
    
    public int solution(String word) {
        StringBuilder sb = new StringBuilder("");
        this.word = word;
        dfs(sb);
        
        return cnt; 
    }
    
}

AI 코드

---

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

---

코드 분석

가중치가 {781, 156, 31, 6, 1} 의 내림차순으로 진행되는 이유는
한 자리가 고정되었을 때,
고정된 단어 앞 순서에 위치하는 단어를 모두 건너뛰어야 하기 때문이다.
만약 첫째 자리에 E 가 온다고 했을 때에는 맨 앞자리가 고정이 되므로
E 로 시작하는 단어보다 앞 순서에 위치하는 모든 단어를 건너뛰어야 한다.
그러나 마지막 자리에 E 가 온다고 했을 때에는
앞자리의 알파벳이 고정이 되지 않은 상태이므로 해당 자릿수만 고려하면 된다.

---

A, E, I, O, U 의 알파벳과 [ ][ ] 의 2의 길이를 가진 사전이 있다.
앞자리가 E 라고 했을 때,
A, AA, AE, AI, AO, AU 의 앞자리가 A 로 시작하는 모든 단어는 건너뛰게 된다.
해당 자리가 고정이 되면 그 앞자리 알파벳의 모든 경우의 수 (6 개)를 건너뛰게 되는데, 이렇게 건너뛰게 되는 수가 바로 가중치이다.

---

EE 의 순서를 구한다고 한다면,
먼저, 첫째 자리가 E 이므로,
해당 알파벳의 앞자리에 위치하는 알파벳은A 하나가 존재한다.
앞자리가 A 로 고정되었을 때 만들 수 있는 단어의 종류는 6 + 1 개 이다.

두번째 자리가 E 이므로 EA 는 건너뛰어야 한다.
따라서 1 + 1 이 된다.

따라서 최종적으로 9 의 순서를 갖는 단어가 된다.

---

class Solution {
    public int solution(String word) {
        char[] alpha = {'A', 'E', 'I', 'O', 'U'};
        int[] weight = {781, 156, 31, 6, 1};   // 각 자리 뒤에 붙는 단어 수 + 자신

        int answer = 0;
        for (int i = 0; i < word.length(); i++) {
            for (int j = 0; j < alpha.length; j++) {
                if (word.charAt(i) == alpha[j]) {
                    answer += j * weight[i] + 1;   // 앞선 분기 전체 + 자신
                    break;
                }
            }
        }
        return answer;
    }
}

문제 풀이 후기

가중치에 대해서 이해하는 데에 어려움을 느꼈다.
수학적인 사고방식은 타고나는 것일까 하는 생각이 든다.
그래도 예시를 들면서
하나하나 대입해가면서 부딪히다 보니 어느정도 이해는 된다.
앞으로도 이런식으로 풀다 보면
수학적인 사고방식을 기르는 데에 감을 잡을 수 있지 않을까 하는 생각이 든다.