[Programmers] Level 2 : 모음사전

프로그래머스

A, E, I, O, U 순서로 길이가 5이하인 문자열을 만들 수 있다고 한다. 이때 특정 문자열이 몇번째 문자열인지 구해야한다.

제한이 매우 작기에 별도의 규칙을 찾을 필요는 없고, 직접 다 구하는 브루트포스를 돌려주는게 가장 간단해 보인다. 그리고 브루트포스를 돌렸을때 시간복잡도는 O(5^5) 정도 소요된다.

import java.util.*;

class Solution {
    
    private List<String> words = List.of("A", "E", "I", "O", "U");
    private Integer count = 0;
    private Boolean flag = false;
    public int solution(String word) {
        dfs("", word);
        return count-1;
    }
    
    public void dfs(String start, String end) {
        if(start.length() > 5 || flag) return;
        if(start.equals(end)) flag = true;
        count++;
        for(String s : words) {
            dfs(start+s, end);
        }
    }
}