백준 1759. 암호 만들기

문제 : 백준 1759. 암호 만들기

서로 다른 L개의 알파벳 소문자들로 구성되는 비밀번호를 구하세요.

조건

1. L개의 알파벳 소문자로 구성된다.
2. 최소 한 개의 모음(a, e, i, o, u)과 두 개의 자음으로 구성된다.
3. 알파벳은 비밀번호의 알파벳은 오름차순으로 배열되어 있다.
   ex) abc는 가능, bac는 불가능

풀이

강의 내용이 생각이 났던 것인지 우선 전부 생성하도록 시도했다.
그러기 위해서 입력받은 C개의 문자들을 정렬을 하였다. 조건3에서 오름차순으로 배열할 것이라고 했기 때문에

이후 정렬된 알파벳을 자리수에 맞게 하나씩 배치하여 모든 경우의 수를 구해낸다. 사용했던 알파벳은 다시 사용하지 않고 순차적으로 하나씩 방문처리하듯이 경우를 생성할 것이었기 때문에 백트랙킹을 적용하면 되겠다고 생각해서 적용하였다.

종료조건으로는 글자가 4자리를 채우게 된다면 조건2를 판단하면서 추가하거나 종료하도록 작성하였다.

package Day1_Algorithm_Basic;

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

public class boj1759 {
    static int l; // 암호의 자리 수
    static int c; // 알파벳의 종류 수
    static String[] cs; // 알파벳 종류
    static ArrayList<String> ans = new ArrayList<>(); //결과 저장 목록


    static void back(int x, String res) {
        int cnt = 0; // 모음 개수 카운트하는 변수

        // 종료 조건
        if (res.length() == l) {
            for (int i = 0; i < l; i++) {
                char temp = res.charAt(i);
             if (temp == 'a' || temp == 'e' || temp == 'i' || temp == 'o' || temp == 'u') {
                    cnt++; //모음 개수 확인
                }
            }
            // 모음이 하나 이상이고, 자음 개수(자릿수 - 모음 개수)가 2개 이상이면 결과에 추가
            if (cnt >= 1 && l - cnt >= 2) {
                ans.add(res);
            }
            return;
        }

        // 정렬된 cs 배열의 값을 하나씩 추가하는 백트랙킹
        for (int i = x; i < c; i++) {
                back(i + 1, res + cs[i]);
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        l = Integer.parseInt(stk.nextToken()); // 암호의 자리 수
        c = Integer.parseInt(stk.nextToken()); // 알파벳의 종류 수

        stk = new StringTokenizer(br.readLine());
        cs = new String[c];

        for (int i = 0; i < c; i++) {
            cs[i] = stk.nextToken();
        }

        Arrays.sort(cs);

        back(0, "");

        for (String a : ans) {
            System.out.println(a);
        }

    }
}