[BAEKJOON_1759 - JAVA] 암호 만들기

이해가 되지않아 자세한 도움이 필요하거나 오류가 있는 경우 댓글을 남겨주세요.

문제

www.acmicpc.net/problem/1759

1759번: 암호 만들기

 

 

풀이

• 브루트 포스를 통해 조합을 만들어내는 문제.
• 문제 파악은 읽으면서, index를 백트레킹에 넣지 않아 시도횟수 증가.
  모든 문제는 꼼꼼히 읽고 집중을 해서 풀자.
• String의 경우 연산이 많이 읽어나는 경우 효율이 떨어지지만, 시간제한이 2sec로 넉넉한 편이어서 가독성이 좋은 코드로 작성을 했다.

 

 

과정

1. 입력받은 알파벳들을 사전순으로 정렬(Arrays.sort 사용).
2. index 번호와 문자열을 파라미터로 가지는 dfs 호출.
3. 기저 조건은 문자열의 길이가 L이 되는 경우와 자음2개, 모음 1개이상으로 이루어진 경우.
4. 자음 2개와 모음 1개의 검사는 contains, replace와 length를 활용.
   ex) 모음을 한개 이상 포함, 모든 모음을 공백으로 변경 후 길이가 2이상인 경우 true.
5. index가 배열의 범위를 넘는 경우 리턴.
6. 문자열에 현재 인덱스의 알파벳을 붙여서 dfs 호출.
7. 문자욜에 현재 인덱스를 건너뛰어 dfs 호출.
8. 3번의 경우에 부합한 경우 암호로 판단 풀력.

 

 

알고리즘 지식

• 브루트포스
• 조합
• 백트래킹

 

 

JAVA코드

package BaekJoon_2020_12_30__2021_01_06;

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

/**
 * @packageName : BaekJoon_2020_12_30__2021_01_06
 * @fileName : BJ_1759_암호만들기.java
 * @author : Mingeon
 * @date : 2020. 12. 31.
 * @language : JAVA
 * @classification : 브루트포스 알고리즘, 조합론, 백트래킹
 * @time_limit : 2sec
 * @required_time : 14:00 ~ 14:48
 * @submissions : 3
 * @description
 */

public class BJ_1759_암호만들기 {

	static int L; // 암호의 길이
	static int C; // 문자들의 갯수
	static char[] arr;

	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());
		arr = new char[C];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < C; i++) {
			arr[i] = st.nextToken().charAt(0);
		} // End of input

		// 사전순을 위한 정렬
		Arrays.sort(arr);
		dfs(0, "");
	}

	private static String dfs(int idx, String str) {

		if (str.length() == L && isValid(str)) {
			System.out.println(str);
			return str;
		}
		if (idx >= C) {
			return str;
		}

		// 현재 인덱스 포함
		dfs(idx + 1, str + arr[idx]);

		// 현재 인덱스 스킵
		dfs(idx + 1, str);

		return str;
	}

	// 모음 1개 이상, 자음 2개 이상 포함 확인
	private static boolean isValid(String str) {
		if (str.contains("a") || str.contains("e") || str.contains("i") || str.contains("o") | str.contains("u")) {
			str = str.replace("a", "");
			str = str.replace("e", "");
			str = str.replace("i", "");
			str = str.replace("o", "");
			str = str.replace("u", "");
			if (str.length() >= 2) {
				return true;
			}
		}

		return false;
	}

}