[프로그래머스 자바] 모음사전 (Lv.2)

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

 

 

import java.util.*;

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

 

DFS 로 풀었다. 

우선 list에다가 사전순으로 단어를 넣도록 했고, chars에다가 A, E, I, O, U를 미리 지정해놓고 이를 이용하도록 했다. 

초기값을 ""로 하고, 이후로 문자열끼리 + 연산자로 하면 합쳐진다는 것을 이용하여 DFS의 첫 줄에는 list에 넣고, 만약 길이가 5이면 종료하도록 했다. 

 

문자열끼리 더하면 속도가 늦다거나, 완전탐색하면 시간이 걸릴까도 생각을 해 봤는데, 

일단 각 자리수의 길이에 따라 경우의 수가 5 + 25 + 125 + 625 + 3125 로 합쳐도 5천이 안 되어서 시간 내로 가능할거라 보았다. 

 

또 word를 찾을 때 인덱스가 0부터 시작하면 안 맞춰지는 거 아닌지도 고려를 해봤는데, 초기값이 "" 이라서 "A"가 인덱스 1이다. 

 

그 이후로 for문 돌면서 찾으면 break 해서 값을 리턴해주었다.