Q 1759 암호 만들기

💡 문제 요약 및 분석

주어지는 알파벳 소문자들로 가능성이 있는 암호들을 전부 출력하자. 단, 알파벳 순서대로 정렬되어야 하며, (abc는 가능하지만 bac 는 안된다) 최소 한 개의 모음과 두 개의 자음으로 구성되어야 한다.

💡 알고리즘 설계

✅ 백트래킹 조건 : 4자리를 완성하면 종료한다. 완성된 4자리의 문자열에 모음1, 자음2 포함되었는지 확인한 후 조건을 만족하면 정답으로 등록한다.

1. 입력

   • 표준입력 : int L, int C
   • 표준입력 : String[] alphabet
   • StringBuilder

2. 연산

   • backTracking(idx, count, string) 함수로 모든 경우의 수를 확인한다.
   • count == L 일 때, 모음1 자음2 여부를 체크한다. 통과하면 결과로 저장한다. sb.append(string).append("\n");
   • for(int next = idx; next < C; next++) 모든 경우의 수를 확인하지만, 문자가 순서대로 정렬되어 있어야 하기 때문에 이전 인덱스는 고려하지 않아도 된다.

3. 출력

   • StringBuilder 에 저장한 문자열을 전부 출력한다.

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {

    static int L;
    static int C;
    static Set<String> check = new HashSet<>(Arrays.asList("a","e","i","o","u"));
    static String[] alphabet;
    static boolean[] visit;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer input = new StringTokenizer(br.readLine());

        L = Integer.parseInt(input.nextToken());
        C = Integer.parseInt(input.nextToken());
        visit  = new boolean[C];
        sb = new StringBuilder();
        alphabet = br.readLine().split(" ");
        Arrays.sort(alphabet);
        br.close();

        for (int i = 0; i < C; i++) {
            visit[i] = true;
            backTracking(i,1, alphabet[i]);
            visit[i] = false;
        }

        System.out.println(sb);
    }

    static void backTracking(int idx, int count, String str) {
        if (count == L) {
            int vo = 0, co = 0;
            for (int i = 0; i < L; i++) {
                char check = str.charAt(i);
                if (check == 'a' || check == 'e' || check == 'i' || check == 'o' || check == 'u') {
                    vo++;
                } else {
                    co++;
                }
            }
            if (vo >= 1 && co >= 2) {
                sb.append(str).append("\n");
            }
            return;
        }

        for (int next = idx; next < C; next++) {
            if (visit[next] == false) {
                visit[next] = true;
                String result = str + alphabet[next];
                backTracking(next,count + 1, result);
                visit[next] = false;
            }
        }
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(L^2)	O(L)