백준_암호만들기_1759

문제 링크

조건

•   L  : 암호 문자 수, 3~15 이하 자연수
•   C  : 암호로 사용할 수 있는 문자 수, 3~15 이하 자연수
• 완성된 암호는 최소 1개의 모음, 2개의 자음으로 구성되어 있다.

 

접근 방법

• 조합
  • 글자 수가 15 이하 => 조합 dfs를 돌려도 시간초과 나지 X
  • 조합 dfs로 문자 완성되면, 암호 조건(모음 1개, 자음 2개 이상) 체크 후 출력

 

솔루션

public class Main {
	static char[] alpha;
	static boolean[] check;//모음 체크를 위한 배열
	static int L, C;//암호 길이, 문자 개수
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine().trim());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		alpha = new char[C];
		check = new boolean[26];
		check['a'- 'a'] = check['e'- 'a'] = check['i'- 'a'] = check['o'- 'a'] = check['u'- 'a'] = true;
		
		st = new StringTokenizer(br.readLine().trim(), " ");
		
		for(int i = 0; i < C; i++) {
			alpha[i] = st.nextToken().charAt(0);
		}
		
		Arrays.sort(alpha);
		
		combi(0,0,new StringBuilder());
	}
	
	private static void combi(int idx, int cnt, StringBuilder pw) {
		if(cnt == L) {//암호 완성
			int tmp = 0;//모음 개수
			for(int i = 0; i < L; i++) {
				if(check[pw.charAt(i) - 'a']) tmp++;
			}
			
			if(tmp > 0 && L-tmp > 1) {//모음 1개 이상, 자음 2개 이상 확인
				System.out.println(pw.toString());
			}
			return;
		}
		
		for(int i = idx; i < C; i++) {
			combi(i+1, cnt+1, pw.append(alpha[i]));
			pw.deleteCharAt(cnt);
		}
	}

}

 

리뷰

• 평범함 조합 문제