백준 1759 암호 만들기

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

---

코드

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

class Main {
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    static int l;
    static int c;

    public static void dfs(int stage, char[] array, char[] result, int index) throws IOException {
        if(stage==l+1){
            int consonant=0;
            int vowel=0;
            for(char i:result){
                if(i=='a'||i=='e'||i=='i'||i=='o'||i=='u')
                    vowel++;
                else
                    consonant++;
            }
            if(consonant>=2&&vowel>=1) {
                for (char i : result)
                    bw.write(i + "");
                bw.write("\n");
            }
        }
        else if(index+1==c){}
        else{
            for(int i=index+1; i<c; i++) {
                result[stage - 1] = array[i];
                dfs(stage + 1, array, result, i);
            }
        }
    }

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

        String s=br.readLine();
        StringTokenizer st=new StringTokenizer(s);
        l=Integer.parseInt(st.nextToken());
        c=Integer.parseInt(st.nextToken());
        s=br.readLine();
        st=new StringTokenizer(s);
        char[] array=new char[c];
        for(int i=0; i<c; i++)
            array[i]=st.nextToken().charAt(0);
        Arrays.sort(array);
        char[] result=new char[l];
        dfs(1,array,result,-1);
        bw.flush();
    }
}

---

해결 과정

1. 사전 순으로 정렬된 가능한 키 값을 사전 순으로 출력해야 한다. 따라서 첫 번째 자리의 키 값부터 끝번째까지 stage 변수로 표현하고, 이전 index보다 이후의 index만 탐색하게 해서 중복되는 경우를 제거했다. 문제의 가능한 문자들을 받아서 사전 순으로 정렬해둔 뒤 재귀적으로 함수를 호출해서 풀었다.

2. 😁