1759번: 암호 만들기

문제

서로 다른 L개의 알파벳 소문자들로 구성된 암호를 추측하는 문제입니다. 암호는 다음과 같은 조건을 만족해야 합니다.

1. 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있습니다.
2. 암호를 이루는 알파벳은 오름차순으로 배열되어 있습니다. (예: abc는 가능하지만 bac는 불가능)

C개의 문자가 주어졌을 때, 가능성 있는 모든 암호를 사전식으로 출력하는 프로그램을 작성해야 합니다.

• 입력: 첫째 줄에 두 정수 L, C가 주어집니다. (3 ≤ L ≤ C ≤ 15) 둘째 줄에는 C개의 문자들이 공백으로 구분되어 주어집니다.
• 출력: 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력합니다.

풀이: 정렬을 동반한 조합 탐색 및 유효성 검사

배열을 정렬하여 탐색 순서를 강제하고, 시작 인덱스를 매개변수로 전달하는 조합(Combination)의 정석적인 풀이입니다.

• 사전 정렬: 입력받은 C개의 문자를 Arrays.sort()를 통해 사전순으로 정렬합니다. 정렬된 배열을 순차적으로 탐색하면 완성된 암호들도 자연스럽게 사전식으로 도출됩니다.
• 백트래킹 전개 (go 함수):
  • idx는 다음으로 선택할 문자의 인덱스를 의미하며, s는 현재까지 구성된 암호 문자열입니다.
  • 반복문은 항상 전달받은 idx부터 시작하므로 이전에 선택한 문자보다 사전순으로 뒤에 있는 문자만 선택하게 되어 오름차순 조건이 유지됩니다.
• 유효성 검사 최적화 (check 함수):
  • 완성된 길이 L의 문자열을 순회하며 모음(a, e, i, o, u)의 개수(cnt)를 카운트합니다.
  • 별도의 자음 카운트 변수를 둘 필요 없이, 전체 길이에서 모음의 개수를 뺀 값(s.length() - cnt)이 곧 자음의 개수가 된다는 성질을 이용합니다.
  • 모음이 1개 이상이고, 자음이 2개 이상일 때만 true를 반환하여 최종적으로 StringBuilder에 덧붙입니다.

코드

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

public class Main {
    static int l, c;
    static char[] a;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       l = Integer.parseInt(st.nextToken());
       c = Integer.parseInt(st.nextToken());

       a = new char[c];
       st = new StringTokenizer(br.readLine());
       for (int i = 0; i < c; i++) {
          a[i] = st.nextToken().charAt(0);
       }
       
       // 사전순으로 암호를 출력하기 위해 입력된 문자들을 미리 오름차순 정렬
       Arrays.sort(a);

       // 깊이 0, 빈 문자열로 탐색 시작
       go(0, "");

       bw.write(sb.toString());
       bw.flush();
    }

    // idx: 탐색을 시작할 위치, s: 현재까지 만들어진 문자열
    static void go(int idx, String s) {
       // 암호의 길이인 l에 도달한 경우 (기저 조건)
       if (s.length() == l) {
          // 모음/자음 개수 조건을 만족하는지 확인
          if (check(s)) {
             sb.append(s).append("\n");
          }
          return;
       }

       // 현재 인덱스 idx부터 탐색하여 오름차순 유지 (조합)
       for (int i = idx; i < c; i++) {
          go(i + 1, s + a[i]);
       }
    }

    // 완성된 문자열이 최소 1개의 모음과 최소 2개의 자음을 포함하는지 검사
    static boolean check(String s) {
       int cnt = 0; // 모음 개수
       for (char c : s.toCharArray()) {
          if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
             cnt++;
          }
       }

       // 모음이 1개 이상이고, 전체 길이에서 모음을 뺀 자음의 개수가 2개 이상이어야 함
       return cnt >= 1 && s.length() - cnt >= 2;
    }
}

알고리즘 분류

수학 (Mathematics), 브루트포스 알고리즘 (Brute Force), 조합론 (Combinatorics), 백트래킹 (Backtracking)