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

문제

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

1759번: 암호 만들기

설명

조합을 이용해 주어진 C개의 문자로 만들 수 있는 L개의 암호 조합을 구하면 된다.

조합을 구한 뒤에는 모음의 개수가 적어도 1개 이상, 자음의 개수가 2개 이상이 되는 경우만 정답 리스트에 추가하면 된다.

 

아래 조합 포스트를 참고하면 좋다.

[Java] 조합 Combination

전체 코드

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

public class Main {
	static int L, C;
	static String[] arr;
	static boolean[] visited;
	static ArrayList<String> resultList;
	static int[] alpha;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		L = sc.nextInt();
		C =  sc.nextInt();

		sc.nextLine();

		String str = sc.nextLine();

		arr = str.split(" ");
		Arrays.sort(arr);

		visited = new boolean[C];
		resultList = new ArrayList<>();

		combination(0, L);

		StringBuilder sb = new StringBuilder();
		for(int i = 0; i < resultList.size(); i++) {
			sb.append(resultList.get(i) + "\n");
		}

		System.out.println(sb);
	}

	// 조합 백트래킹으로 구현 
	public static void combination(int start, int r) {
		if(r == 0) {
			alpha = new int[123];
			String result = "";
			
			for(int i = 0; i < C; i++) {
				if(visited[i]) {
					result += arr[i];
					alpha[arr[i].charAt(0)]++;
				}
			}
			
			int vowels = alpha['a'] + alpha['e'] + alpha['i'] + alpha['o'] + alpha['u']; // 모음 개수 
			int consonants = L - vowels; // 자음 개수 
			
			if(vowels >= 1 && consonants >= 2) {
				resultList.add(result);
			}

			return;
		} else {
			for(int i = start; i < C; i++) {
				visited[i] = true;
				combination(i+1, r-1);
				visited[i] = false;
			}
		}
	}

}

GITHUB

https://github.com/KwonMinha/BOJ/blob/master/BOJ%231759/src/Main.java

GitHub - KwonMinha/BOJ: Baekjoon Online Judge(Java) 문제풀이