[PS] 암호 만들기 (백준 1759번)

연습 겸 완전탐색 문제를 풀었다가, 생각보다 오래 걸렸다. (조합 때문에)

Python 이용할 때는 itertools 내 Combination 라이브러리를 사용할 수 있었는데, java는 직접 구현해야 했다.

물론 어려운건 아니지만, 처음 직접 해봤더니 조금 헤맸다.

조합 기능을 하는 Combination 클래스를 따로 두었고, 문제를 풀었더니 자꾸 틀렸다.

이상해서 자세히 보니 답안 조건에 모음 1개, 자음 2개 이상 포함이 있었다.

이는 isValid() 메서드를 통해 출력 전 검사를 통해 구현했다.

(검증은 Combination의 책임이 아니라고 생각해서..)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

/* BOJ no.1759번 - 암호 만들기 */
public class Main {

    static int L, C;
    static ArrayList<String> answers;
    static char[] alphas;
    static StringBuffer stringBuffer;
    
    public static void main(String[] args) {
        input();
        
        // 완전탐색 (조합)
        Combination combination = new Combination(alphas);
        
        for (char[] result : combination.getCombinations()) {
            if (isValid(result)) System.out.println(String.valueOf(result));
        }
    }
    
    static boolean isValid(char[] charArray) {
        
        int length = charArray.length;

        boolean isHaveAEIOU = false;
        int cntOfConsonant = 0;
        char currentChar = ' ';
        for (int idx = 0; idx < length; idx++) {
            currentChar = charArray[idx];
            if (currentChar == 'a' || currentChar == 'e' || currentChar == 'i' || currentChar == 'o' || currentChar == 'u') {
                isHaveAEIOU = true;
            } else cntOfConsonant++;
        }
        return isHaveAEIOU && cntOfConsonant >= 2 ? true : false;
        
    }
    
    static void input() {
        Reader reader = new Reader();
        L = reader.readInt();
        C = reader.readInt();
        alphas = new char[C];
        for (int idx = 0; idx < C; idx++) {
            alphas[idx] = reader.read().charAt(0);
        }
        Arrays.sort(alphas);
    }

    // 조합 구현하기
    static class Combination {

        static char[] targetArrayOfChar;
        static ArrayList<char[]> resultArray;

        Combination(char[] targetArrayOfChar) {
            this.targetArrayOfChar = targetArrayOfChar;
            this.resultArray = new ArrayList<>(7000);
        }

        ArrayList<char[]> getCombinations() {
            makeCombinations(0, 0, new char[L]);
            return resultArray;
        }

        void makeCombinations(int cnt, int nextIdx, char[] currentArray) {
            if (cnt >= L) {
                resultArray.add(currentArray);
                return;
            } else if (L - cnt >=  C - nextIdx) {
                for (int idx = nextIdx; idx < C; idx++) {
                    currentArray[cnt++] = targetArrayOfChar[idx];    
                }
                resultArray.add(currentArray);
                return;
            }
            
            char[] nextArray = Arrays.copyOf(currentArray, L);
            nextArray[cnt] = targetArrayOfChar[nextIdx];
            makeCombinations(cnt + 1, nextIdx + 1, nextArray);
            makeCombinations(cnt, nextIdx + 1, Arrays.copyOf(currentArray, L));
        }
    }

    static class Reader {
        static BufferedReader bufferedReader;
        static StringTokenizer stringTokenizer;
        
        Reader() {
            bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        }

        String read() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
                
            }
            return stringTokenizer.nextToken();
        }

        int readInt() {
            return Integer.parseInt(read());
        }
    }
}