백준 1759 / 암호만들기

문제

풀이

설명

• 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다
• 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었어야 한다
• 암호로 사용할 수 있는 문자의 종류는 C가지 이다.
  이 조건을 만족하는 암호를 모두 구하는 문제

코드

import java.util.*;

public class Main {
    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 (i >= alpha.length) return;
        go(n, alpha, password+alpha[i], i+1);
        go(n, alpha, password, i+1);
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        String[] alpha = new String[m];
        for (int i=0; i<m; i++) {
            alpha[i] = sc.next();
        }
        
        Arrays.sort(alpha);
        
        go(n, alpha, "", 0);
    }
}

코드설명

• go(n, alpha, password, i)
• n: 만들어야 하는 암호의 길이
• alpha: 사용할 수 있는 알파벳
• password: 현재까지 만든 암호
• i: 사용할지 말지 결정해야 하는 알파벳의 인덱스
• 정답을 찾은 경우 (문제의 조건에 맞는지 확인 과정은 여기서 필요함)
• n == password.length()
• 불가능한 경우
• i >= alpha.size()

참고 :
출처 : https://www.acmicpc.net/problem/1759