kingsubin

import java.io.*;
import java.util.*;
 
public class boj_1759 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int l, c;
    static char[] a;
    static char[] input;
    static boolean[] v = new boolean[15];
 
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        l = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
 
        a = new char[l];
        input = new char[c];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < c; i++) {
            input[i] = st.nextToken().charAt(0);
        }
 
        Arrays.sort(input);
 
        func(0, 0, 0);
 
        bw.flush();
        bw.close();
    }
 
    static void func(int k, int vowelCount, int consonantCount) throws IOException {
        // base condition
        if (k == l) {
            if (vowelCount >= 1 && consonantCount >= 2) {
                for (int i = 0; i < l; i++) {
                    bw.write(a[i]);
                }
                bw.newLine();
            }
            return;
        }
 
        for (int i = 0; i < c; i++) {
            if (v[i]) continue;
            if (k != 0 && a[k-1] > input[i]) continue;
 
            a[k] = input[i];
            v[i] = true;
 
            boolean isVowel = isVowel(input[i]);
            if (isVowel) vowelCount++;
            else consonantCount++;
 
            func(k+1, vowelCount, consonantCount);
 
            v[i] = false;
            if (isVowel) vowelCount--;
            else consonantCount--;
        }
    }
 
    static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}
 

 

- 백트래킹, 재귀

 

- N과 M 문제처럼 백트래킹으로 풀었다.

- 아니면 c 의 제한이 15 까지니까 현재의 알파벳에 대해 사용할지 말지 O, X 의 관점으로 접근할 수도 있다.

- go (int k, char[] alpha, String pass)

- alpha 배열의 k 번째 index 값을 사용할 지 말지 사용하면 pass에 추가, 아니면 pass 그대로, k + 1 로 다시 호출

 

 

 

 

---

www.acmicpc.net/problem/1759