[BaekJoon] 1759 암호 만들기 (Java)

🔗 문제 링크

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

📝 문제풀이 방법

해당 문제도 앞서 풀었던 backtracking문제들 처럼 DFS를 사용하여 풀이를 하면 쉽게 풀 수 있다.

하지만 문제의 조건에서 최소 한개의 모음, 최소 두 개의 자음으로 구성된 암호를 찾으라는 조건이 있어서 해당 조건을 추가해줘야한다.

저는 모음만 신경 쓰고 자음은 신경 안 쓰다 보니 실행 결과에서 오류들이 발생해서 시간을 많이 뺏겼네요..😥

👨🏻‍💻 작성한 코드

import java.util.*;
import java.io.*;

public class Main {

	static int L;
	static int C;
	static char[] vowels = {'a', 'e', 'i', 'o', 'u'};
	static char[] candidate;
	static StringBuilder result = new StringBuilder();
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		candidate = new char[C];
		
		for (int i=0; i< C; i++) {
			candidate[i] = st.nextToken().charAt(0);
		}
		
		Arrays.sort(candidate);
		
		for (int i=0; i< (C-3); i++) {
			StringBuilder cipher = new StringBuilder();
			cipher.append(candidate[i]);
			if (checkVowel(candidate[i])) dfs(1, i, 1, 0, cipher.toString());
			else dfs(1, i, 0, 1, cipher.toString());
		}
		
		System.out.println(result.toString());
		
	}
	static void dfs(int currentLen, int currentPointer, int numberOfVowels, int numOfConsonant, String cipher) {
		if (currentLen == L) {
			if (1 <= numberOfVowels && 2 <= numOfConsonant) {
				result.append(cipher+"\n");
			}
		}
		else if ((C-currentPointer-1) >= (L-currentLen)) {
			for (int i=(currentPointer+1); i< (C- L + currentLen + 1);i++) {
				if (checkVowel(candidate[i])) dfs(currentLen+1, i, numberOfVowels+1, numOfConsonant, cipher+candidate[i]);
				else dfs(currentLen+1, i, numberOfVowels, numOfConsonant+1, cipher+candidate[i]);
			}
		}
	}
	
	static boolean checkVowel(char c) {
		for (int i=0; i<5; i++) {
			if (c == vowels[i]) {
				return true;
			}
		}
		return false;
	}

}