모음사전

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

문제설명

• 주어진 파라미터: String word
• 반환값: int
• A E I O U 만 사용하여 만들 수 있는 길이 5 이하의 단어 수록
• 첫 단어 A 그 다음 AA 마지막 단어 UUUUU
• 단어 하나 word가 매개변수 → 이 단어가 사전에서 몇번째 단어인지 return
• 알파벳 길이는 1이상 5이하

풀이방식

1. 증가하는 규칙이 있지않을까

   781	156	31	6	1
   A	AA	AAA	AAAA	AAAAA
   E	E	E	E	E
   I	I	I	I	I
   O	O	O	O	O
   U	U	U	U	U

2. DFS로 해결

   • 종료조건: 해당 알파벳이랑 일치하는지 확인
   • 반복조건: A E I O U를 차례대로 더해보기 → dfs 호출

코드

class Solution {
    public int solution(String word) {
        int answer = 0;
        int len = word.length();
        int[] score = new int[]{781, 156, 31, 6, 1};
        
        for(int i = 0; i < len; i++){
            char c = word.charAt(i);
            if(c == 'A'){
                answer += 1;
            }else if(c == 'E'){
                answer += 1 + (score[i] * 1);
            }else if(c == 'I'){
                answer += 1 + (score[i] * 2);
            }else if(c == 'O'){
                answer += 1 + (score[i] * 3);
            }else{
                answer += 1 + (score[i] * 4);
            }
        }
        
        return answer;
    }
}

dfs 활용

class Solution {
    
    static int cnt = 0;
    
    public int solution(String word) {
        String[] str = {"A", "E", "I", "O", "U"};
        return dfs(str, word, "");
    }
    
    private int dfs(String[] str, String target, String current) {
        if (!current.equals("")) {
            cnt++;
            if (current.equals(target)) {
                return cnt;
            }
        }
        if (current.length() == 5) {
            return -1;
        }
        for (String s : str) {
            int res = dfs(str, target, current + s);
            if (res != -1) { 
                return res;
            }
        }
        return -1;
    }
}

---

DFS에 대해서 더 공부해야겠다..