[Eric's 백준] 1759번 - 암호 만들기 - JAVA

안녕하세요! 오늘 풀어볼 문제는

백준 1759번 암호만들기 문제 입니다!

해당 문제는 백트레킹을 이용해서 문제를 풀 수 있습니다!

 

풀이

우선 암호로 만들 수 있는 알파벳을 char[] list 에 넣습니다.

그리고 char[] list 를 알파벳 순으로 정렬합니다.

 

정렬하는 이유는 문제의 출력 부분에서 정렬된 순서로 출력되라고 해서입니다.

그리고 정렬된 알파벳을

 

 

backTracking 메소드를 통해서 메소드를 실행합니다.

실행하면서 start 가 L과 동일해지면,

checkTheCode 이라는 메소드를 통해서

한개의 모음과 두개 이상의 자음이 포함되어있는지 체크하고나서

출력해줍니다.

만약 start 가 L과 동일하지 않는다면

for문을 돌면서 하나 하나씩 list에 있는 알파벳을 char[] code 에 넣어줍니다.

이때 하단의 문제풀이처럼 하나하나 push 해주고,

만약 start == L이 되면 pop을 통해서 나온 값을 checkTheCode 통해서 맞을 경우만 출력해줍니다!

 

 

코드

코드입니다!

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.*;
	public class N1759 {
	static int L, C;
	static char[] list;
	static char[] code;
	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());
	list = new char[C]; // 입력 가능한 알파벳 저장
	code = new char[L]; // 코드로 사용할 알파벳 저장
	// list 에 입력 가능한 알파벳 저장
	st = new StringTokenizer(br.readLine());
	for (int i = 0; i < C; i++) {
	list[i] = st.nextToken().charAt(0);
	}
	// 알파벳 정렬
	Arrays.sort(list);
	backTracking(0, 0); // 조합 시작
	br.close();
	}
	public static void backTracking(int cnt, int start) {
	if (start == L) {
	if (checkTheCode()) { // 조건에 맞을 경우에만 출력
	System.out.println(code);
	}
	return;
	} else {
	for (int i = cnt; i < C; i++) {
	code[start] = list[i];
	backTracking(i + 1, start + 1);
	}
	}
	}
	/***
	* 최소 한개의 모음, 최소 2개의 자음인지 확인
	* @return : 해당 code 가 문제 조건에 맞으면 true, 만약 틀리면 false
	*/
	public static boolean checkTheCode() {
	int vowel = 0;
	int consonant = 0;
	for (char x : code) {
	if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') {
	vowel++;
	} else {
	consonant++;
	}
	}
	if (vowel >= 1 && consonant >= 2) {
	return true;
	}
	return false;
	}
	}

view raw N1759.java hosted with ❤ by GitHub