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

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

브루트포스, 백트래킹 문제다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1759 {

	static int L, C;
	static boolean[] visited;
	static StringBuffer sb = new StringBuffer();

	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());
		char[] arr = new char[C];
		visited = new boolean[C];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < C; i++) {
			arr[i] = st.nextToken().charAt(0);
		}

		Arrays.sort(arr);

		perm(arr, 0, L);
	}

	static void perm(char[] arr, int i, int n) {
		if (i == n) {
			int vowel = 0;
			for (int k = 0; k < n; k++) {
				if (sb.charAt(k) == 'a' || sb.charAt(k) == 'e' || sb.charAt(k) == 'i' || sb.charAt(k) == 'o'
						|| sb.charAt(k) == 'u') {
					vowel++;
				}
			}

			if (vowel >= 1 && n - vowel >= 2)
				System.out.println(sb);
			return;
		} else if (i == 0) {
			for (int k = 0; k < C; k++) {
				visited[k] = true;
				sb.append(arr[k]);
				perm(arr, i + 1, n);
				visited[k] = false;
				sb.deleteCharAt(i);
			}
		} else {
			char previous = sb.charAt(i - 1);
			int idx = 0;
			while (arr[idx] != previous)
				idx++;

			for (int k = idx + 1; k < C; k++) {
				if (!visited[k]) {
					visited[k] = true;
					sb.append(arr[k]);
					perm(arr, i + 1, n);
					visited[k] = false;
					sb.deleteCharAt(i);
				}
			}
		}
	}

}

순열 알고리즘을 약간 변형해서 사용했다.

 

우선 알파벳 C개를 입력받아 char arr[]에 저장하고, 알파벳 순으로 정렬 해둔다.

 

그리고 순열을 출력하는 함수 perm을 실행한다.

 

perm(arr,i,n)에서

i==0인 경우, 즉 현재 0글자인 경우는

arr[]에 있는 C개의 알파벳 중 하나를 선택하여 문자열sb에 추가하고, 다음 perm(arr,i+1,n)을 수행하고 돌아온다.

 

i!=n && i!=0 인 경우(코드에서 else부분)는

오름차순으로 글자를 만들기 위해서, 이전에 선택했던 알파벳을 뽑은 다음

그 알파벳보다 순서가 뒤인 글자 중 하나를 선택하여 문자열sb에 추가하고, 다음 perm(arr,i+1,n)을 수행하고 돌아온다.

 

(C개의 알파벳이 들어있는 char arr[]는 입력받은 직후 오름차순으로 정렬을 해 두었기 때문에,

이전에 선택했던 알파벳이 들어있는 index를 찾아, 그 다음 인덱스부터 시작해서 글자를 선택하면 된다)

 

마지막으로 i==n인 경우, 글자를 모두 선택한 경우는

모음의 개수를 세고

모음이 1개 이상, 자음이 2개 이상이라면 해당 문자열sb을 출력하도록 한다.