[Java] 프로그래머스(level-2) - 모음 사전

문제 풀이

---

이번 문제는 재귀(DFS)를 이용해 풀 수 있다.

아이디어 도출

문자가 정해진 단어 안에서 어떤 규칙이 있는지 살펴보자.

1   A
2   AA
3   AAA
4   AAAA
5   AAAAA
6   AAAAE
7   AAAAI
8   AAAAO
9   AAAAU
10  AAAE 
11  AAAEA
12  AAAEE
13  AAAEI
14  AAAEO
15  AAAEU

재귀를 통해 깊이우선탐색하는 것과 유사하지 않은가? 그래서 생각해낸 아이디어는 다음과 같다.

• 모음인 A, E, I, O, U를 모두 탐색하면서 재귀를 통해 문자열을 5의 길이만큼 만들어가는 조합을 적용한다.

모든 경우의 수를 구해야 주어진 word의 순서를 구할 수 있으니 재귀함수를 통해 5의 길이까지의 모음의 모든 경우를 리스트에 담아둔 후, 리스트에서 선형 탐색으로 word의 순서를 찾으면 된다.

다음으로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성 코드

---

import java.util.*;

class Solution {

    // A,E,I,O,U 모음 배열과 최대길이가 될 상수 선언
    static final String[] words = new String[]{"A", "E", "I", "O", "U"};
    static final int MAX_LENGTH = 5;

    // 모든 모음을 경우의 수를 담을 List
    static List<String> list;

    public int solution(String word) {
        
        // 주어진 word가 몇번째 순서인지를 담을 변수
        int answer = 0;

        list = new ArrayList<>();

        // 재귀 함수 호출
        recursion(word, "", 0);

        // 재귀함수 종료 후, 선형탐색으로 word의 순서를 찾는다.
        int size = list.size();
        for(int i=0; i<size; i++) {
            if(list.get(i).equals(word)) {
                answer = i;
                break;
            }

        }

        return answer;

    }

    /**
     * 모음 문자열 배열을 완전탐색하며 모든 모음을 깊이 우선으로 탐색할 재귀함수
     * 모음의 모든 조합을 만들어야 word의 순서를 찾을 수 있다.
     */
    static void recursion(String word, String str, int depth) {

        // 길이가 5가 되면 탐색을 종료한다.
        if(depth == MAX_LENGTH) {
            return;
        }

        // 모든 조합의 수를 List에 담는다.
        list.add(str);
        
        // A,E,I,O,U를 탐색하며 재귀호출
        for(int i=0; i<words.length; i++) {
            recursion(word, str+words[i], depth+1);
        }
        
    }


    public static void main(String[] args) {
        
        Solution sol = new Solution();
        
        // String word = "AAAAE";
        // String word = "AAAE";
        String word = "EIO";

        sol.solution(word);

    }

}

회고

- —

출처

- —

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.