99클럽 코테 스터디 7일차 TIL : 완전탐색(프로그래머스 84512번)

 

 

모음사전

 

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

 

 

---

⭐나의 풀이

 

💡 아이디어) 
1. 완전탐색 알고리즘

 

전체 경우의 수가 모음5개를 조합한 수이기 때문에, 4천개를 넘지않음

 

한 자리 단어: 5개 (A, E, I, O, U)
두 자리 단어: 5×5=25개
세 자리 단어: 5×5×5=125개
네 자리 단어: 5×5×5×5=625개
다섯 자리 단어: 5×5×5×5×5=3125개

 

완전탐색 알고리즘으로 찾아도 시간적으로 괜찮을거라 예상했다.

재귀함수를 활용해보자.

 

✔ 최종 제출한 코드)

import java.util.ArrayList;
import java.util.List;

class Solution {
    static List<String> words = new ArrayList<>();  // 가능한 모든 단어를 저장할 리스트
    static char[] arr = {'A', 'E', 'I', 'O', 'U'}; // 사용할 모음 배열
    
    int solution(String word) {
        
        generateWords("", 0); // 빈 문자열부터 단어 생성 시작
        int answer = words.indexOf(word) + 1; 
        
        return answer;
    }
    
    // 단어 생성 메서드
    static void generateWords(String current, int depth) {
        if (depth > 5) return; // 최대 5자리까지만 생성
        if (!current.isEmpty()) words.add(current); // 빈 문자열이 아닌 경우 리스트에 추가

        for (char c : arr) {
            generateWords(current + c, depth + 1); // 재귀적으로 단어를 생성
        }
    }
}

 

결과

---

 ⭐오늘의 회고

 

처음에 수학적으로 풀려고 규칙을 찾느라 시간을 낭비했다.

 

한글자씩 확인해서 얼마나 늘어나는지 규칙을 찾고 더해볼려고 했는데

생각해보니 재귀함수 (dfs)를 사용하면 아래것 까지 모두 탐색되어서 내가 규칙을 찾을 필요가 없었다.ㅠㅠ

 

풀기전에 어떤 알고리즘을 사용해야할지 신중히 고려해봐야지