[백준] 1759번 : 암호 만들기

문제

1759번: 암호 만들기

 

접근 방식

백트래킹으로 조건을 체크해가며 암호를 만들어주는 문제다.

 

암호는 다음과 같은 조건을 체크해줘야한다.

• 암호는 사전순으로 오름차순으로 정렬되어야 한다.
• 모음은 하나 이상, 자음은 2개 이상 포함되어야 한다.

 

그래서 입력으로 받은 문자 배열을 사전순으로 정렬한 후에

백트래킹으로 조합을 해주면서 모음과 자음을 카운트하여

파라미터로 들고 다니면 된다.

 

계속해서 조합을 하다 원하는 암호의 길이를 만족하면

모음과 자음수가 조건을 만족하는지 체크하고

만족하면 출력해주고 그렇지 않다면 넘어가면 된다.

 

풀이

public class Main {

	static int l, c;
	static char[] chars, password;
	static StringBuilder sb = new StringBuilder();

	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());

		st = new StringTokenizer(br.readLine());
		password = new char[l];
		chars = new char[c];

		for (int i = 0; i < c; i++) {
			chars[i] = st.nextToken().charAt(0);
		}

		Arrays.sort(chars);

		solve(0, 0, 0, 0);

		System.out.println(sb);
	}

	static void solve(int size, int start, int vo, int co) {
		if (size == l) {
			if (vo > 0 && co > 1) sb.append(new String(password)).append("\n");
			return;
		}

		for (int i = start; i < c; i++) {
			password[size] = chars[i];

			boolean isVowel = isVowel(chars[i]);
			int nv = isVowel ? vo + 1 : vo;
			int nc = !isVowel ? co + 1 : co;

			solve(size + 1, i + 1, nv, nc);
		}
	}

	static boolean isVowel(char c) {
		return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
	}
}