프로그래머스 - 모음사전(java)

재귀를 통해서 풀어보았다.

 

최대 3천개까지임으로 점화식을 세워도 됬었지만 재귀가 끌려서 재귀호출로 풀었다.

 

총 재귀로 리스트에 담아준 뒤 sort시킨 이후 , 몇번째 인덱스인지 뽑는 방법을 사용했다.

 

import java.util.*;

class Solution {
    private static List<String> list = new ArrayList<>();
    private static char[] arr = {'A', 'E', 'I', 'O', 'U'};
    private static StringBuilder sb = new StringBuilder();

    public int solution(String word) {
        // 전체 리스트를 재귀적으로 생성
        for (int i = 1; i <= 5; i++) {
            recur(0, i);
        }

        // 사전순으로 정렬
        Collections.sort(list);

        // 몇 번째 인덱스에 해당하는지 확인
        return list.indexOf(word) + 1;
    }

    private static void recur(int index, int depth) {
        if (index == depth) {
            // sb 내용을 리스트에 추가
            list.add(sb.toString());
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);            // 문자 추가
            recur(index + 1, depth);      // 다음 재귀 호출
            sb.deleteCharAt(sb.length() - 1); // 마지막 문자 제거 (원상 복구)
        }
    }
}

 

 

 

여기서 외워야 할 부분은 sb.deleteCharAt(sb.length()-1) 을 해주어야 하는 부분이다.