문제

풀이 과정

브루트 포스 문제. 단 아무 생각 없이, 전부 찾으면 시간초과가 일어날 수 밖에 없다. 해당 문제에서는 아예 문제에 백트래킹 할 부분을 미리 암시하였다.

• 자음 연속 3번
• 모음 연속 3번
• L 문자가 반드시 있어야 함.
  이것과는 별개로, 알파벳에 대하여 일일히 접근하는 역시도 스택오버플로우가 일어날 수 있기 때문에 나의 경우에는, 자음인 경우, 모음인 경우, 그리고 L 인 경우, 총 3 가지의 경우로 통합하여 계산하니 정답이라고 나왔다.

해당 풀이는 다음과 같다.
1. 총 _ 의 갯수를 일단 찾는다.
2. _ 이 변화할 수 있는 모든 경우의 수를 구한다.
2-1. 알파벳을 일일이 하면 스택오버플로우가 날 수 있으니, 크게 자음 = 1 , 모음 = 2 그리고 L 로 3가지 경우로만 나누어 접근했다.
2-2. L 과 자음을 나눈 이유는, L 또한 자음이므로 진행과정에서 중복이 날 수 있다.
2-3. 문제의 조건에 맞게, 자음 연속 3개, 모음 연속 3개, L이 없는 문자열을 제외한다.
3. 해당 문제는 문자의 중복을 허용하므로, 자음인 경우와 모음인 경우를 찾아 모든 경우의 수를 곱해준다. (혹시 모르니 long 처리할 것)

정답

import java.util.Scanner;

public class Main {
    static int blankCnt;
    static String vowel = "AEIOU";
    static long ans = 0;
    static char[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        arr = sc.next().toCharArray();
        blankCnt = 0;
        for(int i=0; i<arr.length; i++) if(arr[i] == '_') blankCnt++;

        findBlank(0,0);
        System.out.println(ans);
    }

    private static void findBlank(int idx, int cnt) {
        if(cnt>=blankCnt) {
            calculate();
            return;
        }

        for(int i=idx; i<arr.length; i++) {
            if(arr[i] == '_') {
                // 자음
                arr[i] = '1';
                findBlank(i+1, cnt+1);
                // 모음
                arr[i] = '2';
                findBlank(i+1, cnt+1);
                arr[i] = 'L';
                findBlank(i+1, cnt+1);
                arr[i] = '_';
            }
        }
    }

    private static void calculate() {
        int check = checkThreeTimes();
        if(check == 0) {
            long total = 1;
            for(int i=0; i<arr.length; i++) total *= arr[i] == '1' ? 20 : arr[i] == '2' ? 5 : 1;
            ans+=total;
        }
    }


    private static int checkThreeTimes () {
        int st = 0;
        int ed = 2;
        // L값 체크
        boolean isL = false;
        while(ed<arr.length) {
            // 모음 갯수
            int v = 0;
            // 자음 갯수
            int c = 0;
            for(int i=st; i<=ed; i++) {
                 if(arr[i] == 'L') isL = true;
                 if(vowel.indexOf(arr[i])>=0 || arr[i] == '2') v++;
                 else c++;
            }

            // 모음 3개로 인한 반환
            if(v >=3) return 1;
            // 자음 3개로 인한 반환
            else if(c>=3) return 2;
            st++;
            ed++;
        }
        // L값이 존재하며 자음 모음에 연속성 없음
        if(isL) return 0;

        return -1;
    }
}