[BOJ 1759] 암호 만들기(G5)

📍 문제 

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

 

 

📍 문제 풀이 

가능한 문자를 조합하여 갯수를 구하는 문제 -> 백트래킹

가능한 문자를 조합하여 가능한 문자열을 모두 구하는 문제 -> 백트래킹 + 브루트포스

때문에 이 문제는 백트래킹 + 브루트포스 문제라고 판단했다.

 

 

주어진 문자 배열에서 `L`개를 뽑을 때까지 값을 채워나간다.

만약 `L`개를 뽑았다면 그 수가 가능성 있는 암호인지 판단해 가능성 있는 수라면 출력

static void dfs(int start, int cnt) {
		if (cnt == L) {
			if (isValid()) {
				System.out.println(passwords);
			}
			return;
		}
		for (int i = start; i < C; i++) {
			passwords[cnt] = alphabet[i];
			dfs(i + 1, cnt + 1);
		}

	}

 

 

주의해야하는 조건

1. 최소 한 개의 모음, 최소 두 개의 자음
2. 알파벳이 증가하는 순서

`isValid` 메서드를 통해 자음과 모음의 갯수를 파악해 가능성있는 암호인지 판단하고,

문자를 입력받을 시점에 정렬을 통해 알파벳이 증가하는 순서대로 문자열을 생성할 수 있도록 구현했다.

 

📍 전체 코드

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

public class boj_1759 {
	static int L,C, cnt;
	static char[] alphabet;
	static char[] passwords;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		alphabet = br.readLine().replace(" ", "").toCharArray();
		passwords = new char[L];
		Arrays.sort(alphabet);

		dfs(0, 0);

	}

	static void dfs(int start, int cnt) {
		if (cnt == L) {
			if (isValid()) {
				System.out.println(passwords);
			}
			return;
		}
		for (int i = start; i < C; i++) {
			passwords[cnt] = alphabet[i];
			dfs(i + 1, cnt + 1);
		}

	}

	public static boolean isValid(){
		int vowels = 0;	// 모음
		int consonants = 0;	// 자음

		for (char c : passwords) {
			if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
				vowels++;
			} else {
				consonants++;
			}
		}

		if (vowels >= 1 && consonants >= 2) {
			return true;
		}
		return false;
	}
}

---

🙋🏻 다시 한 번 더 알고 넘어가기

일반적으로 배열을 println 메서드로 출력하면 [타입@주소] 형식을 가진다.

배열의 값 자체를 출력하기 위해서는 반복문을 통해 직접 출력하는 방식과 Arrays.toString(배열이름)이 있다.

String[] strings = {"A", "P", "P", "L", "E"};
System.out.println(strings);	// [[Ljava.lang.String;@35bbe5e8]
System.out.println(Arrays.toString(strings));	// [A, P, P, L, E]

int[] nums = {1, 2, 3, 4, 5};
System.out.println(Arrays.toString(nums));	// [1, 2, 3, 4, 5]

boolean[] types = {true, false, false, true};
System.out.println(Arrays.toString(types));	// [true, false, false, true]

 

 

예외적으로 char 배열은 println 메서드로 출력하면 각 요소가 구분자 없이 그대로 출력된다. 

import java.util.Arrays;

public class Print_test {
	public static void main(String[] args) {
		char[] chars = {'a', 'p', 'p', 'l', 'e'};
		System.out.println(chars);	// [apple]

		String[] strings = {"A", "P", "P", "L", "E"};
		System.out.println(strings);	// [[Ljava.lang.String;@35bbe5e8]
		System.out.println(Arrays.toString(strings));	// [A, P, P, L, E]
	}
}