[백준] code.plus(브루트포스-재귀,JAVA)1759번, 암호 만들기

문제 링크

1759번: 암호 만들기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

 

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에 핵심은

1. 알파벳을 오름차순으로 사용하여 암호를 만드는 것

2. 최소 한 개의 모음(a,e,i,o,u)와 최소 두 개의 자음이 사용되어야 한다는 것

3. 중복되는 알파벳은 사용하지 못한다.

 

배열

alphabet : 암호를 만드는데 사용되는 알파벳 값 저장

 

check : 알파벳들이 사용되었는지 확인하는 값 저장

 

result : 암호의 각 알파벳 값 저장

 

위에 check, num, result와 재귀를 통해 암호의 경우의 수를 만들었습니다.

 

재귀 과정 중 암호가 최소 한 개의 모음과 최소 두 개의 자음을 가지고 있는지를 확인하였습니다.

 

if문을 사용해서 모음 a, e, i, o, u가 사용되면 모음 카운터가 올라가고 자음이 사용되면 자음 카운터가 올라가게 하였습니다.

 

암호가 완성되었을 때 모음 카운터는 0보다는 커야하고, 자음 카운터는 1보다는 클 때 암호가 완성되었다고 판단하였습니다.

 

위 조건이 만족하면 StringBuilder에 값을 저장한 뒤 BufferdWriter를 통해 한 번에 모두 결과로 출력하였습니다.

 

문제에 해결알고리즘은

1. alphabet 배열을 오름차순 정렬합니다.

2. 재귀를 통해 중복되지 않고 암호에 들어갈 알파벳을 찾습니다.

3. 재귀 중 모음의 개수와 자음의 개수를 증가하도록 하였습니다.

4. 암호에 들어갈 알파벳을 result[]에 저장합니다.

5. 재귀가 L번 반복되었을 때 모음의 개수와 자음의 개수가 조건에 맞게 들어갔다면 StringBuilder에 저장합니다.

5. 재귀 종료시 StringBuilder에 저장된 값을 모두 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 이용하여 배열의 들어갈 수 있는 알파벳들을 저장하였습니다.
• 조건의 맞는 암호의 모든 경우의 수를 구하는code 함수를 만들었습니다.
• BufferedWriter에 조건에 맞는 암호들을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• code는 재귀를 사용하여 조건에 맞는 암호의 모든 경우의 수를 구하였습니다.
• code에서 재귀 중 자음과 모음이 사용되면 카운팅해서 조건에 맞게 설정하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static char[] alphabet;		//암호에 들어갈 알파벳 배열
	public static char[] result;		//암호의 알파벳 값 배열
	public static boolean[] check;		//알파벳 사용되었는지 확인하는 배열
	public static int L,C;
	public static StringBuilder sb = new StringBuilder();	//결과
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화----------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	L = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	alphabet = new char[C];
    	result = new char[L];
    	check = new boolean[C];
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<C;i++) {
    		alphabet[i] = st.nextToken().charAt(0);
    	}
    	Arrays.sort(alphabet);		//알파벳 오름차순 정렬
    	code(0,0,0,0);		//함수 실행
    	bw.write(sb.toString() + "\n");		//결과 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //------------조건에 맞는 암호 만드는 경우의 수 구하는 함수----------
    public static void code(int vowel, int consonant, int depth,int cur) {
    	if(depth==L) {		//암호가 완성되었을 때
    		if(vowel>0 && consonant>1) {	//조건에 맞았을 때
        		for(int i=0;i<L;i++) 	//암호 StringBuilder에 저장
        			sb.append(result[i] + "");
        		sb.append("\n");
    		}
    		return;
    	}
        //---------암호에 들어갈 알파벳 탐색--------
    	for(int i=cur;i<C;i++) {
    		if(!check[i]) {		//사용되지 않은 알파벳일 경우
    			check[i] = true;
    			char temp = alphabet[i];
    			result[depth] = temp;
                	//알파벳이 자음일 때
    			if(temp=='a' || temp =='e' || temp=='i' || temp=='o' || temp=='u')
    				code(vowel+1, consonant, depth+1, i+1);
    			else
                	//알파벳이 모음일 때
    				code(vowel,consonant+1,depth+1,i+1);
    			check[i] = false;
    		}
    	}
    	
    }
}