[코딩테스트 + Java] 모음사전 - 프로그래머스 Lv.2

🔗 문제 링크

프로그래머스 - 모음사전

---

📌 문제 설명

'A, E, I, O, U'로 구성된 길이 1~5의 문자열 중에서 사전 순으로 정렬된 단어 목록이 존재한다. 주어진 단어가 이 목록에서 몇 번째인지 찾아야 한다.

예시

• "AAAAE" → 6번째
• "EIO" → 1189번째

---

💡 문제 접근

모든 경우의 수를 미리 생성해서 리스트에 담고, 해당 단어의 인덱스를 구하는 완전탐색 방식으로 접근한다.

총 경우의 수는 5자리까지이므로
5^1 + 5^2 + 5^3 + 5^4 + 5^5 = 3905
완전탐색으로 충분히 커버 가능하다.

---

✅ 핵심 아이디어: 백트래킹 (Backtracking)

• 길이 1~5의 모든 문자열을 사전순으로 생성
• StringBuffer를 사용하여 문자열 조합 생성
• 리스트에 저장하고, target이 발견되면 조기 종료

---

🧠 코드 설명

static List<String> list = new ArrayList<>(Arrays.asList(""));
static char[] v = "AEIOU".toCharArray();

public static void backtrack(StringBuffer path, int depth, String target){
    if (depth > 5) return;

    String current = path.toString();
    if (depth >= 1) list.add(current);
    if (current.equals(target)) return;

    for (char c : v){
        path.append(c);
        backtrack(path, depth + 1, target);
        path.deleteCharAt(depth);
    }
}

• depth > 5: 단어 길이 초과 시 종료
• list.add(current): 길이 1 이상인 경우만 저장
• target.equals(current): 목표 단어 찾으면 탐색 중단
• deleteCharAt(depth): 백트래킹 핵심 (직전 문자 제거)

---

🎯 전체 코드

package week01.Yoepee;

import java.util.*;

public class PG_84512 {
    // 만들어질 수 있는 최대 단어 길이
    static int MAX_LENGTH = 5;
    // 모음 사전 만들어지는 목록
    // 빈문자 고려해서 index 계산하려고 "" 초기값으로 추가
    static List<String> list = new ArrayList<>(Arrays.asList(""));
    // 알파벳 모음 배열
    static char[] v = "AEIOU".toCharArray();

    // 완전탐색을 통해 모음사전 순회
    public static void backtrack(StringBuffer path,int depth, String target){
        // 최대 글자수를 초과하면 종료
        if(depth > MAX_LENGTH) return;

        String current = path.toString();
        // 단어의 길이가 1 이상이면 저장
        if (depth >= 1) list.add(current);
        // 현재 단어가 주어진 단어라면 순회 종료
        if (current.equals(target)) return;

        for (char c: v){
            // 새로운 모음 추가
            path.append(c);
            // 신규 모음 기준으로 모음사전 재귀
            backtrack(path, depth+1, target);
            // 기존 값으로 초기화 시켜야지 sb가 제대로 동작함
            path.deleteCharAt(depth);
        }
    }

    public static int solution(String word) {
        StringBuffer sb = new StringBuffer("");
        backtrack(sb, 0, word);

        int answer = list.indexOf(word);
        return answer;
    }
}

 

---

🔍 실행 결과

public static void main(String[] args) {
        // 기댓값 : 6
        System.out.println(solution("AAAAE"));
        // 기댓값 : 10
        System.out.println(solution("AAAE"));
        // 기댓값 : 1189
        System.out.println(solution("EIO"));
    }

 

---

🧹 개선 포인트

• 불필요한 "" 초기값 제거: 리스트에 빈 문자열을 넣을 필요는 없음
• 정렬 없이 순회 가능: 백트래킹 자체가 사전순으로 문자열을 생성하므로 별도 정렬 불필요
• 더 빠른 계산식 접근법도 가능: 각 자리에 대해 사전 순서 계산하여 바로 인덱스를 구하는 수학적 풀이도 존재

---

✨ 마무리

이번 문제는 완전탐색과 백트래킹에 익숙해지기 좋은 예제입니다. 특히 문자열 조합을 생성할 때 StringBuffer와 deleteCharAt을 적절히 활용하는 것이 포인트입니다.