[백준 알고리즘] 1759번 암호만들기

백준 알고리즘

암호 만들기(1759번)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	12503	5493	3915	44.088%

문제

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

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

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

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입력 1 복사

4 6
a t c i s w

예제 출력 1 복사

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

먼저 모든 암호는 사전순이므로 배열에 알파벳들을 넣은후 정렬을 해주었다.

문제 풀이 전략으로는 완전탐색 재귀호출 방법을 이용했다. 모든 경우의 수를 탐색해가면서 조건에 맞을경우 해당 값을 출력하고, 아닐경우 함수를 종료시키는 방식이다. 중요한 포인트는 '조건'을 찾는것이다. 정답을 출력하는 조건, 함수 탈출 조건(모든 재귀함수에는 탈출조건이 필수적이다). 사용한 조건은 다음과 같다.

• 현재 완성된 암호가 L 의 길이 && 문제 요구조건(자음, 모음 갯수) 가 맞아떨어질경우 출력

• 탐색하고자 하는 alphabet 배열의 index가 배열 크기보다 클경우 탈출

또한 완전 탐색을 위해서 재귀함수를 이용하였는데, 다음과 같이 설계하였다.

• index값을 매개변수로 받아 char 배열에 접근하여 해당 값을 사용 => 해당 문자를 패스워드에 사용하겠다.

• 아무 값 변화 없이 Index 값만 증가 => 해당 문자를 패스워드에 사용하지 않겠다.

package practice;
​
import java.util.Arrays;
import java.util.Scanner;
​
public class Question1759 {
    static int L;
    static int C;
    static char[] alphabet;
​
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt();
        C = sc.nextInt();
        alphabet = new char[C];
​
        for (int i = 0; i < C; i++) {
            alphabet[i] = sc.next().charAt(0);
        }
​
        Arrays.sort(alphabet);
​
​
        solve(0, "");
    }
​
    public static void solve(int idx, String password) {
        if (password.length() == L && check(password)) {
            System.out.println(password);
            return;
        }
​
        if (idx >= C) return;
​
        solve(idx + 1, password + alphabet[idx]);
        solve(idx + 1, password);
    }
​
    public static boolean check(String password) {
        int ja = 0;
        int mo = 0;
​
        for (int i = 0; i < password.length(); i++) {
            char tmp = password.charAt(i);
            if (tmp == 'a' || tmp == 'e' || tmp == 'i' || tmp == 'o' || tmp == 'u') mo++;
            else ja++;
        }
​
        return (mo >= 1 && ja >= 2);
    }
}
​

해당 코드에서 주의할 점이 한가지 있는데, solve() 함수의 순서이다. solve(idx +1, password) 와 solve(idx + 1, password+alphabet[idx]) 두 함수의 실행 순서를 바꾸게 될 경우 DFS 탐색 과정동안 alphabet 탐색 순서가 역전이 되기때문에 최종 출력 결과가 역정렬 된 상태로 출력이 되게 된다는 점이다.

그 이유는 solve(idx + 1, password)를 계속 실행시킨 이후 실행되는 다음 함수에서는 idx가 마지막 알파벳을 가르키고 있기 때문이다.