[프로그래머스] 모음 사전 - Java

문제 설명

 

코딩테스트 연습 - 모음사전

 

풀이 회고

해당 문제는 DFS를 이용하여 풀이할 수 있었습니다. 우선 문제에서 요구하는 것은 'A', 'E', 'I', 'O', 'U'로만 이루어져 있는 길이 1이상 5 이하의 단어 사전(사전순으로 정렬됨)에서 특정 단어를 찾고자 할 때 해당 단어가 몇 번째 단어인지를 구하는 것입니다.

 

DFS를 통하여 A, E, I, O, U 사전순으로 조합된 단어들을 탐색했는데, 이때 하나의 단어(예를 들어, 'A')로부터 시작해서 사전순으로 단어를 하나씩 추가하면서(String concat 이용) 해당 단어에 대해 Numbering(cnt++)을 했습니다. 이후 'A'로 시작한 단어들을 모두 탐색을 하고나서는(해당 DFS 탐색을 모두 마치고나서는) 또 다른 단어로 시작하는 DFS 탐색을 시작하도록 했습니다. 즉, A, E, I, O, U 각각의 단어로 시작하는 총 5번의 DFS 탐색을 시행하는 것입니다.

 

탐색을 하면서 목표하는 단어(target)와 일치할 경우 전역변수 result에 현재 단어 번호(cnt)를 할당시켜주었습니다. 단어의 개수는 1개 이상 5개 이하이므로 단어의 개수가 만일 5를 초과하면 해당 깊이 우선 탐색의 분기를 종료시키도록 했습니다.

 

제 풀이에서는 5번의 DFS 탐색을 진행하는 중간에 찾고자 하는 단어를 찾았음에도 불구하고 남은 DFS 탐색을 그대로 시행하고 있지만, 찾고자 하는 단어를 찾은 이후에 별도로 flag 설정을 해준다면 중간에 프로그램을 종료시켜 불필요한 탐색을 방지할 수 있겠습니다.

 

 

전체 소스 코드

class Solution {
    String target;
    int cnt;
    int result;

    public int solution(String word) {
        target = word;
        cnt = 1;
        dfs("A");
        dfs("E");
        dfs("I");
        dfs("O");
        dfs("U");

        return result;
    }

    public void dfs(String word) {
        if (word.length() > 5) {
            return;
        }

        if (target.equals(word)) {
            result = cnt;
            return;
        }

        cnt++;

        dfs(word.concat("A"));
        dfs(word.concat("E"));
        dfs(word.concat("I"));
        dfs(word.concat("O"));
        dfs(word.concat("U"));
    }
}

 

 

참고자료

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