프로그래머스 - 모음사전

모음 사전 : https://school.programmers.co.kr/learn/courses/30/lessons/84512#

---

Problem

---

Solve

5개의 문자로 길이 5이하의 단어를 만들어 주어진 word의 순번을 반환하는 문제입니다.

경우의 수가 5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 3905의 경우의 수가 나오게 되고 단어의 길이와 문자 개수가 적었기 때문에 완탐으로 풀수 있을 거라 생각했습니다.

풀이

5개의 알파벳을 배열로 선언하고 각 알파벳과의 조합을 만들어 재귀로 돌려서 조합된 단어를 list에 저장합니다.
그리고 단어를 사전순으로 정렬하여 list에 들어있는 word의 index를 반환했습니다.
(재귀를 돌때, 첫 줄에 단어를 list에 저장하기 때문에 list의 0번 index에는 빈칸이 있습니다.)

---

Code

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
class Solution {
    public int solution(String word) {
        char[] alp = new char[]{'A','E','I','O','U'};
        List<String> words = new ArrayList<>();
        compare(alp, words, "", 0);
        
        Collections.sort(words);
        
        int answer = 0;
        for(int i=0;i<words.size();i++){
            if(words.get(i).equals(word)){
                answer = i;
                break;
            }
        }
        return answer;
    }
    
    void compare(char[] alp, List<String> words, String word, int depth){
        words.add(word);
        if(depth >= 5) return;
        
        for(char a : alp){
            compare(alp, words, word+a, depth+1);
        }
    }
}

---

Result

---

Reference