모음 사전 (DFS)

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

프로그래머스

 

 

문제 풀이

 DFS로 사전을 만든 뒤, 문제에서 요구하는 word의 순서를 리턴해주면 된다.

 

 

처음 작성한 코드 (정답 코드)

import java.util.*;

class Solution {
    public int solution(String word) {
         String[] alphabet = {"A", "E", "I", "O", "U"};
        Stack<String> include = new Stack<>();
        List<String> dic = new ArrayList<>();

        for (int i = 0; i < alphabet.length; i++) {
            dfs(alphabet, i, include, dic);
        }
        
        return dic.indexOf(word) + 1;
    }
    
    public static void dfs(String[] alphabet, int i, Stack<String> include, List<String> dic) {

        include.push(alphabet[i]);

        StringBuilder str = new StringBuilder();

        for (String inner : include) {
            str.append(inner);
        }

        dic.add(str.toString());

        for (int j = 0; j < alphabet.length; j ++) {

            if (include.size() == alphabet.length) continue;

            dfs(alphabet, j, include, dic);
        }

        include.pop();
    }
}

 

 

더 좋은 코드

 사실 모든 사전을 구성한 뒤, 정답을 찾는거보다 사전을 순서대로 구성하며 word를 비교해, 그 순서를 찾는게 시간 복잡도를 줄일 수 있다. DFS를 중간에 멈추는 방법을 생각을 못 해서 일단 위와 같이 짰는데, 다른 사람들의 풀이를 참고하면서 코드를 수정해봤다.

 

import java.util.*;

class Solution {
    public int solution(String word) {
        String[] alphabet = {"A", "E", "I", "O", "U"};
        Stack<String> include = new Stack<>();
        List<String> dic = new ArrayList<>();

        for (int i = 0; i < alphabet.length; i++) {
            dfs(alphabet, i, include, dic, word);
        }

        return dic.indexOf(word) + 1;
    }
    
    // dfs의 리턴 형식을 boolean으로 변경
    public static boolean dfs(String[] alphabet, int i, Stack<String> include, List<String> dic, String word) {

        include.push(alphabet[i]);

        StringBuilder str = new StringBuilder();

        for (String inner : include) {
            str.append(inner);
        }

        dic.add(str.toString());

        // 사전에 추가한 단어가 word와 같다면 사전 편성 종료
        if (str.toString().equals(word)) {
            include.pop();
            return true;
        }

        for (int j = 0; j < alphabet.length; j ++) {

            if (include.size() == alphabet.length) continue;

            // dfs 중 word를 찾았다면 더 이상 탐색 하지 않음
            if (dfs(alphabet, j, include, dic, word)) return true;
        }

        include.pop();
        return false;
    }
}

 

위와 같이 수정하면, 

 

 

만약 word가 "AAAAE"로 주어졌을때, 전체 노드 방문 숫자가 3905번에서 10번으로 줄어든다.