백준 1759 암호 만들기 Java

재귀 호출을 통한 완전 탐색으로 해결할 문제인 암호 만들기 문제이다.

암호의 길이 n이 주어지고 c개의 알파벳이 주어진다.

 

이 c개의 알파벳으로 길이가 n이면서 최소 한 개의 모음과 두 개의 자음을 포함한 암호를 만들면 된다.

우선 문제의 조건대로 알파벳들을 String 배열에 넣고 정렬을 한다.

 

그리고 재귀 호출을 통해 모든 경우를 탐색해볼 메소드를 작성한다.

필요한 파라미터 변수들은

암호의 길이 -> int n

알파벳 배열 -> String [] alpha

암호 -> String password

인덱스 -> int i

 

암호를 만들 때

모든 알파벳을 다 써보기 위해서는 두 가지 경우를 메소드에 적어주면 된다.

인덱스 i의 알파벳을 사용하는 경우, 사용하지 않는 경우

 

이 두 가지의 경우를 모두 재귀 호출해주면

알파벳 c개를 통해 해 볼 수 있는 모든 조합의 암호를 다 만들어 볼 수 있다.

호출할 것을 생각해보면 가지치기하듯이 모든 경우의 암호를 쭉쭉 만드는 형태를 나타낸다.

 

암호가 언제까지고 만들어질 수 없기 때문에

불가능한 경우를 처리해 줘야 한다.

인덱스인 i가 알파벳 배열인 alpha의 길이와 같거나 넘을 때 리턴해준다.

 

정답인 경우는

만들어진 암호의 길이가 입력받은 암호의 길이 n과 같을 때이다.

문제의 조건 중에 최소 모음 1개와 자음 2개를 포함해야 하므로

길이가 n일 때 따로 검사한 후 출력하면 된다.

 

import java.util.Arrays;
import java.util.Scanner;
 
public class Q1759 {
    public static boolean check(String password) {
        int ja = 0;
        int mo = 0;
        for (char x : password.toCharArray()) {
            if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
                mo += 1;
            } else {
                ja += 1;
            }
        }
        return ja >= 2 && mo >= 1;
    }
    
    public static void go(int n, String [] alpha, String password, int i) {
        if(password.length() == n) { 
            if(check(password)) { //모음 자음 개수 검사
                System.out.println(password);
            }
            return;
        }
        if(alpha.length <= i) 
            return;
        
        go(n, alpha, password+alpha[i], i+1); //사용하는 경우
        go(n, alpha, password, i+1); //사용하지 않는 경우
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int c = scan.nextInt();
        scan.nextLine();
        String [] alpha = scan.nextLine().split(" ");
        
        Arrays.sort(alpha);
        go(n, alpha, "", 0);
    }
}