자바(백준) 1759 암호 만들기

오답 노트 & 새로 알게 된 점

보자마자 백트래킹 생각이 나는 문제였다.

 

문제를 잘 읽어야한다. 

최소 한 개의 모음 + 최소 두 개의 모음으로 이루어진 사전식으로 가능한(=정렬) 암호이다.

 

처음에 나는 암호 중에 모음이 하나라도 있으면 되는거네 라고 생각을 했다.

그러나 생각해보니 모음만 있으면 그것도 조건을 만족할 수 없다... 생각을 좀 깊이하는 버릇을 들여야겠다..

 

아무튼 그래서 암호가 될 수 있는 경우의 수를 구하고, 위 조건을 만족시키는 것만 구하면 된다.

 

백트래킹을 잘 알고 있다면 어렵지 않은 문제이다.

 

---

코드

package BackTracking;
 
import java.io.*;
import java.util.*;
 
public class BOJ1759 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int L, C;
    static char A[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        L = atoi(st.nextToken());
        C = atoi(st.nextToken());
 
        A = new char[C + 1];
 
        st = new StringTokenizer(br.readLine());
 
        for (int i = 1; i <= C; i++) {
            A[i] = st.nextToken().charAt(0);
        }
 
        Arrays.sort(A, 1, C + 1);
 
        pro(1, 1, "");
 
        System.out.print(sb);
    }
 
    private static void pro(int start, int cnt, String s) {
        if (cnt == L + 1) {
            if(possible(s)){
                sb.append(s).append("\n");
                return;
            }
        }
 
        for (int i = start; i <= C; i++) {
            String new_s = s + A[i];
            pro(i + 1, cnt + 1, new_s);
        }
    }
 
    static boolean possible(String s) {
        int vo = 0, nonvo = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == 'a' || s.charAt(i) == 'e' ||
                    s.charAt(i) == 'i' || s.charAt(i) == 'o' ||
                    s.charAt(i) == 'u') vo++;
            else nonvo++;
        }
 
        return vo >= 1 && nonvo >= 2;
    }
}