[백준] 1759번 : 암호 만들기 - 자바(JAVA)

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

1759번: 암호 만들기

 

문제 해석

암호로 동작하는 보안시스템을 만드려고 한다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한개의 모음(a,e,i,o,u)와 최소 두 개의 자음으로 주성되어 있습니다.

암호는 알파벳이 증가하는 순서로 배열됩니다.

위의 규칙을 따르는 암호를 모두 출력하세요

 

문제 풀이 전 설계

1. R개의 알파벳을 조합을 이용하여 L개를 뽑는다.

2. 모음이 1개이상 자음이 2개이상인 조합들만 StringBuilder에 담아 출력한다. (나머지는 return = 백트레킹)

 

조합전에 정렬을 한번 해주어야 알파벳이 증가해야 하는 순서로 배열가능

코드

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

public class Main_1759_암호만들기 {

	static char[] alphabet;
	static int passwordLength, numberOfAlphabet;
	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(), " ");
		passwordLength = Integer.parseInt(st.nextToken());
		numberOfAlphabet = Integer.parseInt(st.nextToken());

		alphabet = new char[numberOfAlphabet];
		char[] combinatedArray = new char[passwordLength];

		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < numberOfAlphabet; i++) {
			alphabet[i] = st.nextToken().charAt(0);
		}

		Arrays.sort(alphabet);
		combination(0, 0, combinatedArray);
		System.out.println(sb);

	}

	static void combination(int cnt, int start, char[] combinatedArray) {
		if (cnt == passwordLength) {

			if (!isValid(combinatedArray)) {
				return;
			}

			String temp = new String(combinatedArray);
			sb.append(temp + "\n");
			return;
		}
		for (int i = start; i < numberOfAlphabet; i++) {
			combinatedArray[cnt] = alphabet[i];
			combination(cnt + 1, i + 1, combinatedArray);
		}
	}

	private static boolean isValid(char[] combinatedArray) {

		int vowelsCount = 0;
		int nonVowelsCount = 0;

		for (char e : combinatedArray) {
			if (isVowels(e)) {
				vowelsCount++;
				continue;
			}
			nonVowelsCount++;
		}

		if (vowelsCount < 1 || nonVowelsCount < 2) {
			return false;
		}

		return true;
	}

	private static boolean isVowels(char tempAlphabet) {
		return (tempAlphabet == 'a' || tempAlphabet == 'e' || tempAlphabet == 'i' || tempAlphabet == 'o'
				|| tempAlphabet == 'u');

	}

}