프로그래머스 | LV.2 모음 사전 - 완전 탐색 (Java)

⬛ 프로그래머스 | LV.2 모음 사전 - 완전 탐색

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

프로그래머스

문제 설명

---

💚문제 접근 방식

• 문제에서 길이 5이하 문자열을 알파벳 모음으로만 구성한다고 되어있다. 즉, 5가지 모음을 잘 조합해서 길이 5의 문자열을 구성해야 한다.
• A → AA → … UUUUU 이런 식으로 뻗어간다고 되어 있으므로 DFS로 깊이 5까지 쭉 탐색하면서 (A~U) 모음 순대로 문자열을 이어붙여 구성하는 방식이라는 것을 알 수 있다.
• 특히 입출력 예시를 보면 “AAAAE” = 6번쨰, “AAAE” = 10번쨰라고 되어 있는데, 그림처럼 깊이 5까지 모든 문자열을 빠짐없이 만들어봐야 해당 문자열이 몇 번째 단어인지 명확하게 알 수 있다. 

풀이 설명

• 모든 문자열을 구성해봐야 입력으로 주어진 문자열이 몇 번째 단어인지 파악할 수 있기 때문에 ‘완전탐색’으로 모든 문자열을 깊이 5까지 빠짐없이 구성하면서 풀어야 하는 문제라고 생각했다.
• DFS로 깊이 5까지 모음 5가지로 구성된 문자열을 쭉 형성하며 ArrayList<String> 에 담았다.
• 형성된 ArrayList의 size()만큼 돌면서 입력으로 주어졌던 word 값과 동일한 String 값이 담겨있다면 그때의 index를 리턴하여 풀었다.

💚 제출 코드

import java.util.*;

class Solution {
    static List<String> list;
    static String[] alpha = {"A", "E", "I", "O", "U"};
    //DFS
    static void DFS(int lv, String str){
        list.add(str);
        if(lv==5) return;
        
        for(int i=0; i<5; i++){
            DFS(lv+1, str+alpha[i]);
        }
    }
    
    public int solution(String word) {
        int answer = 0;
        
        list = new ArrayList<>();
        DFS(0, "");
        for(int i=0; i<list.size(); i++){
            if(list.get(i).equals(word)){
                return i;
            }
        }
        
        return answer;
    }
}