모음사전

문제이해에 한시간을 쏟았다.

결론을 낸건 DFS를 사용해서 풀어야 한다는 것이다.

내 이론은 이렇다.

A시작점을 기준으로 왼쪽으로 X는 추가하지않는것이고, Ax, AAx, AAAx, AAAAx, AAAAA, AAAAE,AAAAI, AAAAO, AAAAU, 다시 한칸 더 위로가서, AAAEx, AAAEA, AAAEE.... 이런식으로 완전탐색으로 풀면되겠다 싶었다.

하지만 나의 능력의 한계에 부딪혀 결국 치트키를 썼다.

 

그래서 얻어낸 코드를 보며 코드의 설명을 해보겠다.

public class Main {
    static final char[] WORDS = {'A', 'E', 'I', 'O', 'U'};
    static final int MAX_LENGTH = 5;
    public static int solution(String word) {
        int answer = 0;

        List<String> elements = new ArrayList<>();
        //다섯개문자 각각에 대해 dfs메서드를 호출해 가능한 모든 단어 생성
        for(int i=0; i<WORDS.length; i++){
            dfs(elements, String.valueOf(WORDS[i]));
        }
        //elements 를 순회하면서 word의 인덱스 구하고 +1 해준다.
        for(int i=0; i<elements.size(); i++){
            if(elements.get(i).equals(word)){
                answer = i + 1;
                break;
            }
        }

        return answer;
    }
    //elements = 모든단어 저장, str = 현재까지 생성된 문자열
    static void dfs(List<String> elements, String str){
        //str길이가 5초과하면 재귀중지
        if(str.length() > MAX_LENGTH) return;
        //elements에 현재 str이 없다면 추가 (중복없음)
        if(!elements.contains(str)) elements.add(str);
        //다섯 개의 문자각각에 대해 재귀 호출
        for(int i=0; i<WORDS.length; i++){
            dfs(elements, str+WORDS[i]);
        }
    }

    public static void main(String[] args) {
        String word = "E";
        String word2 = "AAAE";
        String word3 = "I";
        String word4 = "EIO";
        String word5 = "AAAOE";
        System.out.println(solution(word));	// 782
        System.out.println(solution(word2)); // 10
        System.out.println(solution(word3)); //1563
        System.out.println(solution(word4)); //1189
        System.out.println(solution(word5)); //24
    }
}

코드를 보며 dfs메서드가 재귀되면서 어떻게 되는지를 그려가며 해봤다. 그려보니 이제서야 이해가 갔다. 근데 도저히 내머리로는 이걸 코드로 짜는게 안될거같긴하지만 익숙해지려 노력해보면 언젠가 될거라 믿는다...!

코드를 일단 눈에 익혀보자!