boj 1759

문제 풀이

암호는 서로다른 l개 알파벳 소문자로 구성
최소 모음 1개로 구성 또한 암호들은 정렬 된 조합
암호들 모두 구하기

1. 문자 입력 받고 오름차순 정렬
2. 백트래킹 현재 현재 문자 자음 인지 모음인지 구분하여
   (c개중 l 개 뽑는 조합)
   전체 l 이고 모음 2개 자음 1개이면 출력
   중복 조합이 x니 방문 체크하고
   모음 수 자음수 전체수 count 하며 s에 더하며 백트래킹 하기

코드

public class boj1759 {
    private  static char [] cs;
    private static int l;
    private static int c;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 입력 l c
         l = Integer.parseInt(st.nextToken());
         c = Integer.parseInt(st.nextToken());

        // c 의 공백 문자열
        cs = new char[c];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<c; i++){
            cs[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(cs); //1. 문자 입력 받고 오름 차순



        // 조합
        // c 개중 자음 2 개를 뽑아라
        boolean[] visited = new boolean[c];
        comP(0,0, 0,0,visited, "");


    }
    // 6개 중 4개를 뽑을거임
    private static void comP(int idx, int countG,int countC,int count , boolean[] visited, String s){ // 인덱스, 모음 수, 전체 수 , 방문 체크
        if(count == l && countG >=1 && countC >=2){
            System.out.println(s);
            return;
        }
        for(int i=idx; i<c; i++){
            if(!visited[i]){
                visited[i] = true;
                if(cs[i] == 'a' || cs[i] == 'e' || cs[i] =='i' || cs[i] =='o' || cs[i] == 'u' ){
                    comP(i,countG+1,countC,count+1,visited,s+cs[i]);
                }else{
                    comP(i,countG,countC+1,count+1,visited,s+cs[i]);
                }
                visited[i] = false;
            }
        }

    }
}

---

이 문제의 키 포인트는 자음의 개수와 모음의 개수를 count 하여 백트래킹을 돌린다는 것이다.

처음에는 모음의 개수만 돌렸는데 실패가 나왔다
생각해보니 반례로
3 5
a e i o u
면 아무것도 안나와야하는데 (자음이 최소 2개가 아니니)
허나 나왔다. 자음의 개수를 안세고 모음의 개수만 세서

그러니 자음 모음 두개 다 count 하여

if(count == l && countG >=1 && countC >=2){
            System.out.println(s);
            return;
        }

다음 같은 기저조건을 만족하면 출력하고 멈춰주면 된다.