[BaekJoon] 1759 암호 만들기

1.  문제 링크

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

2.  문제

요약

• 암호는 서로 다른 L개의 알파벳 소문자들로 구성되어 있고 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있습니다.
• 또한, 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어 있습니다.
• 암호로 사용할 법한 문자 C개가 주어졌을 때, 가능성 있는 암호들을 모두 구하는 문제입니다.
• 입력: 첫 번째 줄에 3보다 크거나 같고 15보다 작거나 같은 L과 L보다 크거나 같고 15보다 작거나 같은 C가 주어지고 두 번째 줄에는 C개의 문자들이 주어집니다.
• 출력: 각 줄에 하나씩, 사전식으로 가능성 있는 암호들을 모두 출력합니다.

3.  소스코드

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

public class Main {
	static int l, c;
	static char[] alphabets;
	static char[] code;
	public boolean isValid() {
		int consonant = 0; // 자음
		int vowel = 0; // 모음
		for(char i : code) {
			if(i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u') {
				vowel++;
			} else {
				consonant++;
			}
		}
		if(vowel >= 1 && consonant >= 2) {
			return true;
		}
		return false;
	}
	
	public void findCode(int x, int index) {
		if(index == l) {
			if(isValid()) {
				System.out.println(code);
			}
			return;
		}
		for(int i = x; i < c; i++) {
			code[index] = alphabets[i];
			findCode(i + 1, index + 1);
		}
	}
	
	public void getAllPW() {
		Arrays.sort(alphabets);
		code = new char[l];
		findCode(0, 0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		l = Integer.parseInt(input[0]);
		c = Integer.parseInt(input[1]);
		alphabets = new char[c];
		input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < c; i++) {
			alphabets[i] = input[i].charAt(0);
		}
		Main m = new Main();
		m.getAllPW();
	}
}

4.  접근

• 해당 문제는 백트래킹을 이용하여 해결할 수 있습니다.
• 가능한 암호들을 사전순으로 출력해야하므로 주어진 알파벳들을 오름차순으로 정렬합니다.
• L개의 알파벳을 이용하여 암호를 만든다는 의미는 암호의 길이가 L이라는 의미이기 때문에 암호를 나타내는 배열 code의 길이를 L로 지정할 수 있습니다.
• 첫 번째 알파벳부터 시작하여 다음 알파벳을 암호의 다음 알파벳으로, 또한 그 다음 알파벳을 암호의 다음 알파벳으로 설정해가며 4자리 암호를 만들고 해당 암호가 최소 1개의 모음과 최소 2개의 자음으로 이루어져있다면 이를 출력하고 그렇지 않다면 이전으로 돌아가 다음 알파벳을 이용하여 4자리의 암호를 만듭니다.

1. 주어진 알파벳들을 배열 alphabets에 넣어주고 오름차순으로 정렬합니다.
2. 4자리 암호를 나타내는 배열 code를 생성합니다.
3. 첫 번째 알파벳부터 시작하여 4자리 암호를 만들고 해당 암호가 최소 1개의 모음과 최소 2개의 자음으로 이루어져있다면 출력하고 그렇지 않다면 다른 암호를 찾습니다.
   1. 첫 번째 알파벳부터 시작하여 마지막 알파벳까지 반복문을 돌면서 4자리 암호를 찾습니다.
      1. 해당 알파벳을 아직 채워지지 않은 암호의 칸 중 가장 앞에 넣어주고 재귀함수를 통해 4자리 모두 채워질 때까지 알파벳을 넣어줍니다.
   2. 만약 4자리 암호가 완성되었다면 해당 암호가 조건에 만족하는지 확인하고 그렇다면 이를 출력하고 그렇지 않다면 다른 암호를 찾습니다.
      1. 자음의 개수를 나타내는 변수 consonant, 모음의 개수를 나타내는 변수 vowel을 생성하고 모두 값을 0으로 초기화합니다.
      2. 4자리 암호의 각 알파벳들을 돌면서 자음의 개수와 모음의 개수를 찾습니다.
      3. 만약 자음의 개수가 2개 이상이고 모음의 개수가 1개 이상이라면 true를 반환하여 해당 암호를 출력하도록 합니다.
      4. 만약 그렇지 않다면 false를 반환하여 다른 암호를 찾도록 합니다.