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

코드 힌트

DFS로 풀기 (모든 단어 생성 후 indexOf로 찾기)

1. 모든 단어 생성:
   • 재귀 함수를 사용해 가능한 모든 단어를 생성하고 리스트에 저장합니다.
   • 문자열의 길이가 5를 넘으면 재귀 호출을 중단합니다.
   • 길이가 5 이하인 경우, 리스트에 현재 문자열을 추가합니다.
   • 각 재귀 호출에서는 "AEIOU"의 각 문자를 문자열에 추가하며, 이 과정을 반복합니다.
2. 단어 위치 찾기:
   • 모든 단어가 리스트에 저장된 후, 주어진 단어의 위치(index)를 찾습니다.
   • 리스트에서의 위치가 곧 해당 단어가 사전에서 몇 번째로 등장하는지 의미합니다.
   • list.indexOf(word)를 사용해 위치를 찾아 반환합니다.

문자열을 변환하며 일치하는지 확인하기

1. 문자 변환:
   • 주어진 단어의 각 문자를 숫자로 변환하여 비교를 단순화합니다.
   • "A"는 "1", "E"는 "2", "I"는 "3", "O"는 "4", "U"는 "5"로 변환합니다.
2. 순차적 단어 생성:
   • 현재 문자열을 주어진 단어와 일치할 때까지 반복적으로 증가시킵니다.
   • 각 반복에서 문자열의 길이를 확인하고, 길이가 5보다 작으면 "1"을 추가합니다.
3. 단어 변환 및 비교:
   • 문자열을 계속해서 증가시키며, 주어진 단어와 일치하는지 비교합니다.
   • 일치하는 순간 반복을 종료하고, 결과를 반환합니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    
    // 모든 가능한 단어를 저장할 리스트
    static List<String> list = new ArrayList<>();
    
    public int solution(String word) {
        // DFS를 사용해 모든 가능한 단어를 생성
        dfs("");
        // 주어진 단어의 인덱스를 반환 (순서 계산)
        return list.indexOf(word);
    }
    
    // DFS를 통해 재귀적으로 단어를 생성하는 메소드
    public static void dfs(String s) {
        // 단어 길이가 5보다 크면 종료
        if (s.length() > 5) {
            return;
        }
        // 생성된 단어를 리스트에 추가
        list.add(s);
        // 각 모음(AEIOU)을 붙여 새로운 단어를 생성하고 재귀 호출
        for (int i = 0; i < 5; i++) {
            dfs(s + "AEIOU".charAt(i));
        }
    }
}

 

class Solution {
    public int solution(String word) {
        // 초기화: 각 문자를 숫자로 변환 (A=1, E=2, I=3, O=4, U=5)
        StringBuilder currentWord = new StringBuilder();
        word = word.replaceAll("A", "1");
        word = word.replaceAll("E", "2");
        word = word.replaceAll("I", "3");
        word = word.replaceAll("O", "4");
        word = word.replaceAll("U", "5");
        
        int result = 0;
        
        // 주어진 word와 일치할 때까지 반복
        while (!currentWord.toString().equals(word)) {
            result++; // 순서 계산
            
            // 길이가 5보다 작으면 "1"을 추가 (즉, 'A' 추가)
            if (currentWord.length() < 5) {
                currentWord.append("1");
                continue;
            }
            
            // 단어의 각 문자에 대해 마지막 문자를 증가시키는 방식으로 다음 단어 생성
            char[] charArr = currentWord.toString().toCharArray();
            for (int i = 4; i >= 0; i--) {
                charArr[i] = (char) (charArr[i] + 1);
                
                // 문자가 5보다 작다면 다음 문자로 이동
                if (charArr[i] < '6') {
                    break;
                } else {
                    charArr[i] = '0'; // 5를 넘으면 '0'으로 변경
                }
            }
            // 변경된 문자 배열을 다시 문자열로 변환하여 currentWord에 저장
            currentWord.setLength(0);
            
            for (int i = 0; i < 5; i++) {
                if (charArr[i] != '0') {
                    currentWord.append(charArr[i]);
                } else {
                    break;
                }
            }
        }
        
        return result; // 결과 반환
    }
}