[BOJ] 1759 암호만들기 - JAVA

1. 문제

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 

암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 

조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다.

주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

---

2. 풀이

암호가 사전순서이고, 중복되는 것도 없으므로 조합처럼 풀면 된다. (2022.02.20 - [코딩테스트] - 조합과 중복조합)

대신 기저조건(cnt==L)에 다다랐을 때 반복으로 하나하나 돌면서 계산하기 싫어서 파라미터로 vowel을 넣었다. 지금까지 모음이 몇 번 있는지 저장해놓은 변수다. 만약 vowel이 1보다 작거나, 총 암호의 길이에서 vowel을 뺀 값(=자음)이 2보다 작다면 적절한 암호가 아니다.

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

public class BOJ_1759_암호만들기 {
   static int L, C;
   static char[] alphabets;
   static StringBuilder sb = new StringBuilder();

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

      L = Integer.parseInt(st.nextToken());
      C = Integer.parseInt(st.nextToken());
      alphabets = new char[C];

      st = new StringTokenizer(in.readLine());
      for (int i = 0; i < C; i++) alphabets[i] = st.nextToken().charAt(0);
      Arrays.sort(alphabets);

      makePw(0, 0, 0, 0);

      System.out.print(sb);
   }

   private static void makePw(int cnt, int start, int vowel, int flag) {
      if (cnt == L) {
         if (vowel < 1) return;
         if (L - vowel < 2) return;

         for (int i = 0; i < C; i++) {
            if ((flag & 1 << i) != 0) sb.append(alphabets[i]);
         }

         sb.append("\n");
         return;
      }

      for (int i = start; i < C; i++) {
         if ((flag & 1 << i) != 0) continue;
         makePw(cnt + 1, i + 1, isVowel(alphabets[i]) ? vowel+1 : vowel, flag | 1 << i);
      }


   }

   private static boolean isVowel(char ch) {
      return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
   }
}

---

3. 결과

첫번째는 문제 조건(한 개의 모음 두 개의 자음)을 잘못봐서 틀렸고, 두번째는 그냥 코드를 잘못짜서 틀렸다. 이제야 좀 조합이 이해될 것 같다. 

밑의 코드에서 노란 부분이 다음 재귀를 위한 시작관련부분이고, 파란 부분이 현재 상태를 의미한다고 보면 된다.

풀어서 얘기하면 --> cnt+1번째 수를 뽑으러 가는데, i+1부터 탐색을 시작하고, 모음은 지금까지는 (vowel | vowle+1)개 있었으며 지금까지 뽑힌 수는 i포함된 flag에 있다.