백준 1759 암호 만들기 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/1759

풀이는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    static int L,C;
    static char[] arr;
    static BufferedWriter bw;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        String S = br.readLine(); //주어진 입력값 받아오기
        //a t c i s w
        
        S = S.replace(" ", ""); //공백 없에주기
        //atcisw
        
        arr = S.toCharArray(); //String을 char[] 으로 바꿔주기
        //{a, t, c, i, s, w}
        
        Arrays.sort(arr); //알파벳순 정렬
        //{a, c, i, s, t, w}

        backTracking(0, "", 0);

        bw.flush();
        bw.close();
        
    }

    static void backTracking(int depth, String s, int start) throws IOException {
        if(depth == L) {
            if(aeiou(s) >= 1 && L-aeiou(s) >= 2) { 
            //모음 수 1개 이상, 자음 수 2개 이상 둘 다 만족한다면 적어주기
                bw.write(s + "\n");
            }
        }


        for(int i = start ; i < C ; i++) {
            s += arr[i]; //암호에 글자 붙이기
            backTracking(depth+1, s, i+1);
            s = s.substring(0, s.length()-1); // 암호에 붙였던 글자 떼주기
        }

    }



    static int aeiou(String s) {
        char[] arr = s.toCharArray();
        int answer = 0;

        for(char c : arr) {
            if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') answer++;
        }

        return answer;
    }

}

백트래킹 문제이다.
주석으로 설명을 달아놓았다.
요즘 코테를 보면, 백트래킹 + 그래프 문제가 자주 나와서,
해당 영역을 연습해야지 싶다.

처음엔,

if(aeiou(s) >= 1 && L-aeiou(s) >= 2) { //모음 수 1개 이상, 자음 수 2개 이상

위의 로직을 아래와 같이 작성하여

if(aeiou(s) >= 1) { //모음 수 1개 이상

26퍼센트에서 틀렸습니다가 나왔다.
해당 로직으로는,

오직 모음으로만 이루어진 암호는 통과할 수 없지만, 통과하게 되어버린다.

예를 들어 틀린 로직으로 실행하면 반례는 아래와 같다.

input:
3 5
a e i o u
output:
aei
aeo
aeu
aio
aiu
aou
eio
eiu
eou
iou

//옳은 output
output: (아무것도 출력되지 않아야함)

모음으로만 이루어진 암호이므로, 출력되지 않아야 정상이지만 출력되어버린다.

한 15초만 더 자세하게 생각했으면 틀렸습니다 없이 통과했을텐데, 아쉽다.
좀더 꼼꼼하게 읽고 자세하게 봐야겠다.
문제풀이 전에 수도코드, 문제 읽기는 다다익선이라고 생각한다.