[백준]1759번 - 암호 만들기 (JAVA)

알고리즘 & 자료구조/완전탐색

[백준]1759번 - 암호 만들기 (JAVA)

윤도ri 2022. 5. 12. 14:32

| 문제

이 문제는 C개의 알파벳을 탐색하여 중복 없이 L개를 고르는 문제이다. 그러므로 백트래킹을 사용해야 한다는 의미이며

그 방법들 중 DFS를 사용할 것이다.

( * 백트래킹과 DFS 에 대한 자세한 설명은 이전 게시글에 설명해놓았다.)

https://turtle8760.tistory.com/90

| 문제 접근 방식

1. L과 C를 입력받는다 (L: 암호의 자릿수 C: 암호로 사용했을 가능성이 있는 알파벳의 개수)

: 최소 1개의 모음, 최소 두개의 자음이 포함된다.

--> 모음자음 판별하는 메서드 생성

2. 알파벳이 사전 순으로 나열된다.(bac X abc O)

--> Arrays.sort 사용한다.

3. 암호의 각 알파벳을 중복하지 않고 모든 경우의 수를 탐색한다. ( aaci (X) aciw(O) )

1) 재귀를 사용한다. (* 재귀 함수란? 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스)

2) 탐색하고 출력하기 위해서 값을 담을 char배열 arr를 생성한다.

3) L개를 다 고른 후에는 더 이상 재귀가 호출되지 않고 출력되어야 하므로 이를 판단해줄 length 변수를 추가한다.

재귀가 깊어질 때마다 length를 1씩 증가시켜 L과 같아지면 더이상 재귀를 호출하지 않도록 한다

4) 알파벳은 중복되는 알파벳을 제외하고 모든 경우의 수를 탐색해야 한다. 그러므로 재귀를 하면서 이미 방문한 노드 (값)이라면 다음 노드를 탐색하도록 하기 위해 int타입의 level 변수를 추가한다.

ex) arr= {a, c, i, s, t} 암호는 3글자이다.

첫 번째 알파벳: a 그다음 알파벳은 a부터 탐색하는 것이 아니라 c부터 시작하게 된다. 그러므로 다음 재귀에서

level을 1씩 증가시킨다면 앞서 탐색한 알파벳을 제외하고 탐색할 수 있게 된다.

4) 제시된 알파벳 중 조건에 맞는 알파벳만 출력하기 위해서 그 조건의 판단 유무를 결정하기 위해서 C크기의 boolean 타입 visited 변수를 추가한다.

| 출력

bufferedReader와 StringBuilder를 사용했다. (성능의 차이를 고려하여)

import java.io.*;
import java.util.*;

public class FindPw_1759 {
	static char[] arr; //
	static boolean[] visited; //방문 유무 확인
	static int l, c; // 암호자리수, 암호일 가능성있는 알파벳의 갯수 
	
	
	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];
		visited = new boolean[c];
		
		st = new StringTokenizer(br.readLine());
		
		//hasmoreTokens: 사용할 수 있는 토큰이 존재한다면 true 
		for(int i= 0; st.hasMoreTokens(); i++) {
			arr[i] = st.nextToken().charAt(0);
		}
		//문자열 정렬하기 
		Arrays.sort(arr);
		
		dfs(0, 0);
		
		br.close();		
	}
	public static void dfs(int level, int length){
		if(length == l) {
			StringBuilder sb = new StringBuilder();
			int vowel = 0; //모음
			int consonant = 0; //자음
			
			for(int i=0; i<c; i++) {
				if(visited[i]) {
					//모음이라면 
					if(isVowel(arr[i])) {
						vowel++;
					}
					//자음이라면 
					else {
						consonant++;
					}
					sb.append(arr[i]);
				}
			}
			//모음이 1개이상이고 자음이 2개이상이면 출력
			if(vowel >=1 && consonant >= 2) {
				System.out.println(sb);
			}
		}
		else {
           
			for(int i = level; i <c; i++) {
            	//방문된 값만 출력하기 위해서 
				visited[i] = true;
                //중복되지 않도록 탐색하기 위해 i+1 을 해준다.
                //L개가 다 탐색되었는지 판단하기 위해 length +1을 해준다.
				dfs(i+1,length+1);
				visited[i] = false;
			}
		}
		
	}
	
	public static boolean isVowel(char c) {
    //모음이면 true  자음이면 false
		if(c== 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ) {
			return true;
		}
		else {
			return false;
		}
		
	}

}