1759 암호 만들기(자바)

 

 

 

 

 

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


public class Main {
	
	static int N;
	static int M;
	static String input[];
	static boolean check[];
	static String word;
	static StringBuilder result;
	
	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");	
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		check = new boolean [M];
		result = new StringBuilder();
	
		input = new String[M];
		StringTokenizer st1 = new StringTokenizer(br.readLine(), " ");	
	
		for(int i=0;i<M; i++) {
			input[i] = (String) st1.nextToken();
		}
	
		Arrays.sort(input);
	
		dfs(0, 0);
	
	}	
	
	public static void dfs(int start, int depth) {
		
		if(depth==N) {
		
			for(int i=0; i<M;i++) {
			if(check[i]) {
				result.append(input[i]);
			
		    	}
			}
			
			word = result.toString();
			result.setLength(0);
			
			int count = 0;
			
			if(word.contains("a")) count++;
			if(word.contains("o")) count++;
			if(word.contains("u")) count++;
			if(word.contains("e")) count++;
			if(word.contains("i")) count++;
			
			if(1 <= count && count <= N-2) {
				
					System.out.println(word);
				
			}
		}
		
		
		for(int i =start; i<M;i++) {
			
			check[i]=true;
			dfs(i+1, depth+1);
			
			check[i]=false;
		}
	}
}

 

이전에 풀었던 로또문제(백준 6603) 이랑 비슷해서 비교적 수월하게 풀었다.

 

https://happy-fun.tistory.com/196?category=981765 

6603 로또 (java)

 

 

 

dfs 를 이용해서 완성했다.

코드를 설명해보겠다.

 

N : 암호 길이 // 4

M : 입력 받은 문자 개수 //6

input 배열 : 입력 받은 문자를 input 배열에 넣음. 그리고나서 배열을 오름차순 정렬하기 때문에

최종적으로 input 배열에는 

a c i s t w 순으로 저장된다.

 

check 배열과 result 변수는 아래에서 설명하겠다.

 

---------------------------------

 

dfs 메서드를 살펴보자.

우리는 dfs(0,0) 부터 시작한다.

그럼 일단 아래 부분부터 살펴보자.

	for(int i =start; i<M;i++) {
			
			check[i]=true;
			dfs(i+1, depth+1);
			
			check[i]=false;
		}

 

 

dfs(0,0) 이므로, 

start = 0, depth =0 이다.

그리고 check 배열에 설명하자면

타입이 boolean 으로

처음에는 모든 값이 false 로 초기화 되어 있다.

하지만 위에서 보듯이 check 배열의 값을 true 로 바꿔주고 있다.

 

이를 설명해보겠다.

 

input 배열에는 다음과 같이 저장되어 있다.

a c i s t w 

 

만약 check 배열의 값들이 true true false false true true 로 되었다고 하자.

이때 우리는 true 의 값을 가지고 있는 인덱스, 즉 여기서는 0,1,4,5 에 해당하는

input 배열의 값을 찾아서,

즉 a c t w 

출력할 것이다.

 

이게 가능하도록 아래 코드 완성

 

	if(depth==N) {
		
			for(int i=0; i<M;i++) {
			if(check[i]) {
				result.append(input[i]);
			
		    	}
			}
			
			word = result.toString();
			result.setLength(0);
			
			int count = 0;
			
			if(word.contains("a")) count++;
			if(word.contains("o")) count++;
			if(word.contains("u")) count++;
			if(word.contains("e")) count++;
			if(word.contains("i")) count++;
			
			if(1 <= count && count <= N-2) {
				
					System.out.println(word);
				
			}
		}

 

 

depth==N, 즉 여기서는 4를 만족하게 되면

check 배열의 true 값이 4개가 된다.

이때 check 배열의 인덱스에 해당하는 input 배열의 글자를 출력해서

길이가 4인 암호를 출력한다.

 

예를들어,

아래와 같다.

input 배열은 a c i s t w 이고,

그 아래 check 배열의 상태, 그 인덱스에 해당되는 input 배열의 글자이다.

 

 

 

이와 더불어 모음이 1글자 이상, 자음이 2글자 이상인 조건을 만족하는 글자를 최종적으로 출력하게 한 것이다.

 

그리고 여기서 보면, StringBuilder 타입의 result 변수에 글자들을 추가한 다음

String 타입의 word 에 옮겨 담아서 출력하는 것을 알 수 있다.

 

이는, StringBuilder 의 append 메서드를 사용하기 위함이다.

String 타입에서는 글자에 다른 글자를 추가할 때 concat 라는 메서드를 사용하는데,

이 메서드는 2개의 글자를 합쳐서 출력해줄 뿐, A 단어에 B 단어를 붙여서 유지해주지 않는 듯 했다.

그래서 StringBuilder 를 이용해서 글자들을 이어붙이고 다시 String 타입의 word 변수에 옮겨 담았다.

 

 

더불어서 

	result.setLength(0);

이 코드로 result 변수를 초기화 한 뒤, 

새로운 단어를 담도록 했다.

 

 

 

이 사진에서도 볼 수 있지만,

맨 처음에는 t t t t f f 이지만

그 아래는 t t t f t f 이다.

 

즉, 인덱스 3의 위치 t 값이 그 다음에는 f 로 변해있는데,

	for(int i =start; i<M;i++) {
			
			check[i]=true;
			dfs(i+1, depth+1);
			
			check[i]=false;
		}

이 코드에서 보이듯이, dfs() 메서드를 마치고 돌아와서는 다시 false 로 바꾸기 때문이다.