백준 - 암호 만들기

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/1759

 

[문제 설명]

1.모음이 1개 이상

2.자음이 2개 이상

3.암호는 알파벳 순서대로

가능한 모든 암호의 경우의 수를 출력하시오

 

[접근 방법]

각 인덱스별로 알파벳이 있나 없나 확인하는 문제.

시간복잡도는 O(2^n)이 된다. 있나 없나 2가지 경우의 수를 n번 반복하므로.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    static int L,S;
    static char[] charArray;
    static Stack<String> passwordStack = new Stack<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] firstLine = br.readLine().split(" ");
        String[] secondLine = br.readLine().split(" ");
        L = Integer.parseInt(firstLine[0]);
        S = Integer.parseInt(firstLine[1]);
        charArray = new char[S];
        for (int i = 0; i < secondLine.length; i++) {
            charArray[i] = secondLine[i].charAt(0);
        }

        Arrays.sort(charArray);
        makePassword(new StringBuilder(),0,0,0);
        while (!passwordStack.isEmpty()) System.out.println(passwordStack.pop());
    }
    private static void makePassword(StringBuilder sb, int index, int numOfVowels, int numOfConsonants) {
        if (sb.length() == L ) {
            if (numOfVowels >= 1 && numOfConsonants >= 2) passwordStack.add(sb.toString());
            return;
        } else if (index == S || sb.length()+S-index < L) return;     // 배열의 마지막에 도달했거나, 나머지 문자를  모두 추가해도 전체 길이가 L이 안될 때,

        makePassword(sb, index+1, numOfVowels, numOfConsonants);
        if (charArray[index] == 'a' || charArray[index] == 'e' || charArray[index] == 'i' || charArray[index] == 'o' || charArray[index] == 'u') {
            numOfVowels++;
        } else numOfConsonants++;
        makePassword(sb.append(charArray[index]), index+1,numOfVowels,numOfConsonants);
        sb.deleteCharAt(sb.length()-1);
    }
}