99클럽 코테 스터디 9일차 TIL: [프로그래머스] 모음사전

https://school.programmers.co.kr/learn/courses/30/lessons/84512?language=java

프로그래머스

 

조금 헤맸는데 dfs로 쉽게 해결할 수 있는 문제였다.

• dfs로 "A", "E", "I", "O", "U"를 차례대로 이어서 만들어진 각 문자열들을 리스트에 담고, word가 몇 번째 문자열인지 확인하면 된다.
• 이렇게 하면 시간 복잡도는 dfs(O(5^5)) + 완전탐색(O(5^5))이다.

import java.util.*;

class Solution {
    
    String[] words = new String[]{"A", "E", "I", "O", "U"};
    List<String> list = new ArrayList<>();
    
    public int solution(String word) {
        
        dfs("");
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(word)) {
                return i + 1;
            }
        }
        return -1;
    }
    
    public void dfs(String s) {
        if (s.length() == 5) {
            return;
        }
        
        for (int i = 0; i < 5; i++) {
            list.add(s + words[i]);
            dfs(s + words[i]);
        }
    }
}