[BOJ - Gold IV] 즐거운 단어 / ❌

즐거운 단어

1. 제출 코드 (2시간 32분 46초 / DFS)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static String input;
    static long answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        input = br.readLine();
        dfs(0, 0, 0, false, 1);
        System.out.println(answer);
    }

    public static void dfs(int idx, int mo, int ja, boolean l, long count) {
        if(mo >= 3 || ja >= 3) return;
        if(idx == input.length()) {
            if(l) answer += count;
            return;
        }
        char t = input.charAt(idx);
        if(t == '_') {
            dfs(idx + 1, mo + 1, 0, l, count*5);
            dfs(idx + 1, 0, ja + 1, l, count*20);
            dfs(idx + 1, 0, ja + 1, true, count);
        } else {
            if(t == 'A' || t == 'E' || t == 'I' || t == 'O' || t == 'U') {
                dfs(idx + 1, mo + 1, 0, l, count);
            } else {
                if(t == 'L') dfs(idx + 1, 0, ja + 1, true, count);
                dfs(idx + 1, 0, ja + 1, l, count);
            }
        }
    }
}

 

2. 구현 로직

t가 알파벳이라면 각 자음과 모음의 개수를 업데이트하고 L의 여부를 업데이트한다. 확정된 알파벳으로 count의 변화는 없다.

 

만약, t가 "_"일 경우에는 3가지 경우의 수로 나눠진다.

1. "_"가 모음인 경우

모음 개수를 업데이트하고 자음의 개수는 0으로 초기화하며 count는 모음의 개수를 곱해준다.

 

2. "_"가 자음인 경우

자음 개수를 업데이트하고 모음의 개수는 0으로 초기화하며 count는 자음의 개수 - 1을 곱해준다. L은 따로 처리하기 때문에 -1을 해준다.

 

3. "_"가 L인 경우 

자음 개수를 업데이트하고 모음의 개수는 0으로 초기화하며 count는 그대로이며 L을 true로 변경한다.

 

3. 유의할 점

• 경우의 수를 처리할 때, L의 여부를 고민하여 처리해야 될 거 같다.