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

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

프로그래머스

1. 코드

class Solution {
    static int answer = 0;
    static int cnt = 1;
    public int solution(String word) {
        char[] vowel = {'A', 'E', 'I', 'O', 'U'};
        StringBuilder sb = new StringBuilder();
        dfs(word, vowel, sb);
        return answer;
    }
    
    public static void dfs(String word, char[] vowel, StringBuilder sb) {
        if(sb.toString().length() >= 5)
            return;
        for(int i = 0; i < vowel.length && answer == 0; i++) {
            sb.append(vowel[i]);
            if(word.equals(sb.toString())) {
                answer = cnt;
                break;  
            }
            cnt++;
            dfs(word, vowel, sb);
            sb.deleteCharAt(sb.toString().length() - 1);
        }
    }
}

2. 설명

public static void dfs(String word, char[] vowel, StringBuilder sb) {
    if(sb.toString().length() >= 5)
        return;
    for(int i = 0; i < vowel.length && answer == 0; i++) {
        sb.append(vowel[i]);
        if(word.equals(sb.toString())) {
            answer = cnt;
            break;  
        }
        cnt++;
        dfs(word, vowel, sb);
        sb.deleteCharAt(sb.toString().length() - 1);
    }
}

DFS 알고리즘을 사용하여 완전탐색을 진행하였는데 종료조건은 sb의 길이가 5이하여야 한다. 반복문을 통해서 모든 모음에 순차적으로 접근하는데 answer의 값이 0이며 vowel의 길이만큼 진행합니다.

만약 word와 sb가 동일하다면 cnt의 값을 answer에 저장하며 반복문을 종료하여 함수가 종료되게 합니다. 아니라면 cnt의 값을 증가하고 재귀함수를 호출합니다. 재귀함수가 종료된다면 sb의 마지막 문자를 제거합니다.

3. 정리

• DFS 알고리즘을 통해서 쉽게 완전탐색을 구현할 수 있다.

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges