백준 1759번: 암호 만들기

문제 설명

• 주어진 단어로 만들수 있는 경우의 수 중에
  • 오름차순이며
  • 최소 하나의 모음이 들어있으며
  • 최소 두개의 자음이 들어있는

문자열을 구하는 문제입니다.

접근법

• 입력받은 문자열을 정렬한 뒤 조합 경우의 수를 구하고 최소자음과 모음 조건을 확인합니다.

정답

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

public class Main {
	
	static int L;
	static int C;
	static char[] answer;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		answer = new char[L];
		char[] alph = new char[C];
		st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < alph.length; i++) {
			alph[i] = st.nextToken().charAt(0);	
		}
		
		Arrays.sort(alph); // 조합을 구하기 전 정렬을 실행합니다.
		//System.out.println(Arrays.toString(alph));
		Comb(0,0,alph);
	}
	
	public static void Comb(int depth,int start,char[] alph) {

		if(depth == L) { //종료조건
			int vowel_cnt = 0;
			int consonant_cnt = 0;
			for (int i = 0; i < answer.length; i++) {
				// Arrays.stream(arr).anyMatch(i -> i.equals("a")) 
                // Arrays.asList(arr).contains("a");
                switch (answer[i]) {  
				case 'a':
					vowel_cnt++;
					break;
				case 'e':
					vowel_cnt++;
					break;
				case 'i':
					vowel_cnt++;
					break;
				case 'o':
					vowel_cnt++;
					break;
				case 'u':
					vowel_cnt++;
					break;

				default:
					consonant_cnt++;
					break;
				}
			}
            //자음과 모음의 수가 조건에 만족하는지 확인합니다.
			if(vowel_cnt>=1 && consonant_cnt>=2) { 
				System.out.println(answer);
			}
			return;
		}

		for (int i = start; i < C; i++) {
			answer[depth] = alph[i];
			Comb(depth+1,i+1,alph);
		}
	}
}

기타

• Comb(depth+1,i+1,alph);는 되지만 Comb(++depth,++i,alph);는 안되는 이유
  • Comb(depth+1,i+1,alph);는 재귀함수의 인자에 depth+1을 넘겨주고 재귀함수를 호출한 함수의 depth는 아무런 변화가 없습니다.
  • Comb(++depth,++i,alph);는 재귀함수를 호출한 함수의 depth가 1 더해진 채로 유지됩니다.

for (int i = start; i < C; i++) {
	Comb(depth);
    //여기서 depth는 여전히 depth
}
for (int i = start; i < C; i++) {
	Comb(++depth);
    //여기서부터 depth는 depth+1인 상태(for문의 다음에 영향이 간다)
}