[JAVA] 백준 (골드5) 1759번 암호 만들기

링크

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

---

문제 설명

정답률 44.878%

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

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

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

---

입력 예제

4 6
a t c i s w

---

출력 예제

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

---

풀이

백트래킹으로 주어진 알파벳으로 오름차순으로 4자리가 되는 부분 집합을 구하는 문제이다. 재귀를 호출하면서 depth가 L이 될 때까지 재귀를 반복한다. 또한 알파벳이 오름차순으로 정렬되어야 하므로 반복을 시작하는 인덱스도 1씩 증가시킨다.

static void recur(int depth, int start) {
    if (depth == L) {  //depth가 L이 되면 리턴
        if (isSatisfied()) {  //조건을 만족할 경우
            for (char c : arr) {
                sb.append(c);
            }
            sb.append("\n");
        }
        return;
    }
    
    for (int i = start; i < C; i++) {
        arr[depth] = chars[i];
        recur(depth + 1, i + 1);
    }
}

단 조건으로 모음 1개와 자음 2개 이상을 포함하여야 하므로 조건을 만족하는지 불리언을 반환하는 메서드로 조건 충족 여부를 판단한다.

//조건: 모음 1개, 자음 2개 이상
static boolean isSatisfied() {
    int vowels = 0;
    int consonants = 0;
    for (char c : arr) {
        if (isVowel(c)) {
            vowels++;
        } else {
            consonants++;
        }
    }
    return vowels >= 1 && consonants >= 2;
}

//알파벳의 모음 여부 반환
private static boolean isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

전체 코드

//백준
public class Main {

    static StringBuilder sb = new StringBuilder();
    static int L, C;
    static char[] chars;
    static char[] arr;

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        chars = new char[C];
        arr = new char[L];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < C; i++) {
            chars[i] = st.nextToken().charAt(0);
        }
        Arrays.sort(chars);

        recur(0, 0);

        System.out.println(sb);
    }

    static void recur(int depth, int start) {
        if (depth == L) {  //depth가 L이 되면 리턴
            if (isSatisfied()) {  //조건을 만족할 경우
                for (char c : arr) {
                    sb.append(c);
                }
                sb.append("\n");
            }
            return;
        }
        
        for (int i = start; i < C; i++) {
            arr[depth] = chars[i];
            recur(depth + 1, i + 1);
        }
    }

    //조건: 모음 1개, 자음 2개 이상
    static boolean isSatisfied() {
        int vowels = 0;
        int consonants = 0;
        for (char c : arr) {
            if (isVowel(c)) {
                vowels++;
            } else {
                consonants++;
            }
        }
        return vowels >= 1 && consonants >= 2;
    }

    //알파벳의 모음 여부 반환
    private static boolean isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
}