[Algorithm] 🔐白準1759パスワードの作成


0、問題


昨日、崔伯俊(チェ・ボジュン)助教が部屋の鍵をポケットに入れてソウルに持って行くのを忘れたというとんでもない状況に直面した助教たちは、702号に新しい保安システムを設置することにした.このセキュリティシステムは鍵ではなくパスワードで動作するシステムです.
暗号は異なるL個の小文字からなり、少なくとも1つの母音(a、e、i、o、u)と少なくとも2つの補助音からなる.また,配列を好む文字列の助教たちの傾向から,暗号を構成するアルファベットが暗号に増加する順に配列されていると推測される.すなわちabcは可能なパスワードであり、bacはそうではない.
新しいセキュリティシステムでは、助教たちが使用する可能性のあるパスワードにC種類の文字があるという.このアルファベットを手に入れた民植は、英植兄弟が助教たちの部屋に浸透するため、暗証番号を推測しようとした.C文字がある場合は、可能なすべてのパスワードを取得するためのプログラムを作成します.
入力
第1行は2つの整数L,Cを与える.(3≦L≦C≦15)次の行は、C文字をスペースで区切ります.与えられた文字は小文字で、重複はありません.
しゅつりょく
行ごとに1つ、可能なすべてのパスワードを出力しておきます.

1.問題の簡単な説明


C個の異なるアルファベットを使用してLビットのパスワードを作成する必要があります
パスワードには、少なくとも2つの子音と1つの母音が含まれている必要があります.
アルファベットは昇順に並べなければなりません

2.アイデア


💡 2つ以上の子音と1つ以上の母音の関数をチェックします.
💡 アルファベットを配列に挿入し、昇順に並べ替えます.
💡 再帰関数を使用してすべての状況を参照

3.コア解答


1)2つ以上の子音、1つ以上の母音の関数を検査する
if(cons >=2 && vowel >=1)
	return true;
else
	return false;
2)アルファベットを配列に入れて昇順に並べ替える
Arrays.sort(alpha);
3)再帰関数を使用してすべての状況をブラウズする
dfs(pwd+alpha[i],i+1);
dfs(pwd,i+1);

4.コード

import java.io.*;
import java.util.*;

public class BOJ_1759 {
	static int L, C, result[];
	static char alpha[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s[] = br.readLine().split(" ");
		
		L = Integer.parseInt(s[0]);
		C = Integer.parseInt(s[1]);
		
		alpha = new char[C];
		result = new int[C];
		
		s = br.readLine().split(" ");
		
		for(int i=0; i<C; i++)
			alpha[i] = s[i].charAt(0);
		
		Arrays.sort(alpha);
		
		dfs("",0);
			
	}
	
	public static void dfs(String pwd, int i) {
		if(pwd.length() == L && check(pwd)) {
			System.out.println(pwd);
			return;
		}
		if(alpha.length <= i)
			return;
		
		dfs(pwd+alpha[i],i+1);
		dfs(pwd,i+1);
		
	}

	public static boolean check(String pwd) {
		int cons = 0;
		int vowel = 0;
		
		for(char c : pwd.toCharArray()) {
			if(c == 'a' || c == 'e' || c =='i' || c =='o' || c=='u')
				vowel++;
			else
				cons++;
		}
		
		if(cons >=2 && vowel >=1)
			return true;
		else
			return false;
	}
}

5.結果



成功~