[BOJ] 1759번 암호 만들기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int l;
	static int c;
	static char[] arr;
	static char[] password;
	static boolean[] visited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		l = sc.nextInt();
		c = sc.nextInt();
		arr = new char[c];
		password = new char[l];
		visited = new boolean[c];
		for (int i = 0; i < c; i++) {
			arr[i] = sc.next().charAt(0);
		}
		// 오름차순 정렬 여부 검사를 피하기 위함
		Arrays.sort(arr);
		combination(0, 0);
	}
	
	static void combination(int count, int start) {
		if (count == l) {
			if (isValid()) {
				System.out.println(String.valueOf(password));
			}
			return;
		}
		for (int i = start; i < c; i++) {
			password[count] = arr[i];
			combination(count + 1, i + 1);
		}
	}
	
	static boolean isValid() {
		int vowels = 0;		// 모음의 개수
		int consonants = 0;	// 자음의 개수
		
		// 자음과 모음의 개수 확인
		for (int i = 0; i < l; i++) {
			if (password[i] == 'a' || password[i] == 'e' || password[i] == 'i' || password[i] == 'o' || password[i] == 'u') {
				vowels++;
			} else {
				consonants++;
			}
		}
		// 모음이 1개 미만이고 자음이 2개 미만일 경우 조건 불충족
		if (vowels < 1 || consonants < 2) {
			return false;
		}
		return true;
	}
}

📄 해설

• 오름차순 정렬을 피하기 위해 배열을 정렬한 뒤 시작한다.
• 조합 알고리즘을 사용하는 문제로, 조합의 종료 조건 부분에서 암호 가능을 확인하는 메소드를 호출하여 검증
• 오름차순은 검증할 필요가 없어졌으므로, 자음과 모음의 개수만 판단한다