[ 백준 1759번 ] 암호 만들기

1. 문제

1759번: 암호 만들기

 

2. 풀이

전형적인 백트래킹 유형의 문제로, 백트래킹(backtracking)을 이용한 순열만들기 유형의 문제라고 보면 된다. 그렇다면 중요한 것은 어떠한 조건을 만족시켜야 하는가를 잘 정의해야 하며, 해당 조건들은 아래와 같다.

 

• 모음 1개 이상
• 자음 2개 이상
• 사전 순으로 출력
• 길이 C의 문자열 생성

 

사전 순으로 출력해야 하는 조건이 있기 때문에 입력 받은 문자 배열을 오름차순 정렬을 먼저 해주고, 모음 및 자음의 개수는 backtracking 메서드의 매개변수로써 선언해서 사용하였다. 사실 메서드 내부에서 해당 길이를 탐색해주어도 되지만, 제시된 R의 범위가 작을 뿐더러 문자열 내의 모음/자음 개수를 매번 체크하고 싶지 않았기 때문이다.

 

세부 구현은 아래 코드를 참고하자!🚀

 

3. 소스코드

public class Main {
    static int L, C;
    static char[] arr;
    
    /**
     * @param start 다음 요소 탐색 시작 지점
     * @param len 전체 문자열 길이
     * @param vowel 모음 개수
     * @param consonant 자음 개수
     * @param str 탐색 과정에서 만들고 있는 문자열
     */
    static void backtracking(int start, int len, int vowel, int consonant, String str) {
        if (len == L && vowel >= 1 && consonant >= 2) {
            System.out.println(str);
            return;
        }

        for (int i = start; i < C; i++) {
            if (isVowel(arr[i])) {
                backtracking(i + 1, len + 1, vowel + 1, consonant, str + arr[i]);
            } else {
                backtracking(i + 1, len + 1, vowel, consonant + 1, str + arr[i]);
            }
        }
    }

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        L = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        String[] line = br.readLine().split(" ");
        arr = new char[C];
        for (int i = 0; i < C; i++) {
            arr[i] = line[i].charAt(0);
        }
        Arrays.sort(arr);

        backtracking(0, 0, 0, 0, "");

        br.close();
    }
}

GitHub - kwanik-kor/BOJ: Baekjoon Online Judge - explanation of solved problems and complete code