[골드 5] 암호 만들기

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

4 6
a t c i s w

정렬하면

acistw

여기서 앞에서부터 4개 무작위로 어떻게 골라낼까?

아무리 생각해 봐도 모르겠어서 좀 헤맸다

 

 

 

정렬 안 하고

1. dp [C-1]에 모든 경우의 수가 담긴다

2. 모든 경우의  수를 돌면서 (길이 일치 && 모음 개수 자음 개수 합격) 일 시 answer에 add

3. answer을 돌면서 answer.get(i)의 문자열 정렬 ex) bcda -> abcd

4. answer list를 정렬 ex) cdef abcd   -> abcd cdef

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int L, C;
        String[] alphabets;

        st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        alphabets = new String[C];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++)
            alphabets[i] = st.nextToken();

        ////////////////////////////////////////////////////////////////

무난하게 입력받기

        ArrayList<ArrayList<String>> dp = new ArrayList<>();
        ArrayList<String> small_dp;
        ArrayList<String> answer = new ArrayList<>();

        small_dp = new ArrayList<>();
        small_dp.add("");
        small_dp.add(alphabets[0]);
        dp.add(small_dp);

        for (int i = 1; i < C; i++) {
            small_dp = new ArrayList<>();
            for (String tmp : dp.get(i - 1)) {
                small_dp.add(tmp + alphabets[i]);
                small_dp.add(tmp);
            }
            dp.add(small_dp);
        }

        for (String tmp : dp.get(C - 1)) {
            if (tmp.length() == L) {
                int vowel_count = 0;
                int consonant_count = 0;

                for (int j = 0; j < L; j++) {
                    if (tmp.charAt(j) == 'a' || tmp.charAt(j) == 'e' || tmp.charAt(j) == 'i' || tmp.charAt(j) == 'o' || tmp.charAt(j) == 'u')
                        vowel_count++;
                    else
                        consonant_count++;
                }

                if (vowel_count >= 1 && consonant_count >= 2)
                    answer.add(tmp);
            }
        }

        for (int i = 0; i <answer.size(); i++) {
            char[] charArr = answer.get(i).toCharArray();
            Arrays.sort(charArr);
            String result = String.valueOf(charArr);
            answer.set(i,result);
        }

        Collections.sort(answer);

        for (String tmp : answer)
            sb.append(tmp + "\n");

        System.out.println(sb);
    }
}