백준 1759 (암호 만들기) - 조합알고리즘

문제

---

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

 

 

 

 

 

풀이

---

우선 주어진 알파벳을 사전순으로 정렬을 해야한다.(증가하는 순서로 배열되었다고 문제에서 말했기 때문)

 

abc 와 bac 는 안된다는 것을 보면 순서 상관없이 알파벳이 증가하는 방향으로 비밀번호를 작성해야한다는 것을 알수 있다.

 

따라서 조합알고리즘을 이용해서 풀어야한다.

 

모음이 1개 , 자음이 2개 이상이어야 하므로 갯수를 세어주는 방식으로 했다.

conpulake.tistory.com/72?category=857046

순열, 조합, 부분집합, 멱집합 정리

위에서 조합알고리즘을 참고하면 좋겠다.

cnt_consonant : 모음 갯수를 센다.

cnt_vowel : 자음 갯수를 센다.

satic void combination(List<String> alphabet, List<String> result, int size,
								int r, int index, int cnt_consonant, int cnt_vowel) {
	
	if(r == 0 && cnt_consonant >= 1 && cnt_vowel >= 2) {
		String password = result.toString().replaceAll(" ", "").replaceAll(",",  "").replaceAll("\\[|\\]", "");
		sb.append(password).append("\n");
		return;
	}
	
	for(int i = index ; i < size ; i++) {
		String alph = alphabet.get(i);
		
		if("aeiou".contains(alph)) {
			cnt_consonant++;
		}
		else {
			cnt_vowel++;
		}
	
		result.add(alph);
		combination(alphabet, result, size, r - 1, i + 1, cnt_consonant, cnt_vowel);
		result.remove(result.size() - 1);
		
		if("aeiou".contains(alph)) {
			cnt_consonant--;
		}
		else {
			cnt_vowel--;
		}
	}
}

 

 

위에서 모음갯수를 아래의 코드를 통해 셌다.

if("aeiou".contains(alph)) {
	cnt_consonant++;
}
else {
	cnt_vowel++;
}

String 의 contains 메소드를 이용하여 aeiou 안에 포함된 값일 경우엔 모음이므로 cnt_consonant++ 을해주고

자음인 경우는 cnt_vowel++ 을 해준다.

 

result.remove(result.size() - 1);

이 코드 이후에는 추가 되었던 알파벳이 지워진 상태이므로 

해당 알파벳이 모음인지 자음인지를 파악한 뒤 갯수를 빼준다.

 

 

<전체코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();

	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		List<String >result = new ArrayList<String>();
		List<String> alphabet = new ArrayList<String>();
		
		int L = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(bufferedReader.readLine());
		for(int i = 0 ; i < C ; i++) {
			alphabet.add(st.nextToken());
		}
		Collections.sort(alphabet);
		
		combination(alphabet, result, C, L, 0, 0, 0);
		
		System.out.println(sb);
	}
	
	static void combination(List<String> alphabet, List<String> result, int size,
									int r, int index, int cnt_consonant, int cnt_vowel) {
		
		if(r == 0 && cnt_consonant >= 1 && cnt_vowel >= 2) {
			String password = result.toString().replaceAll(" ", "").replaceAll(",",  "").replaceAll("\\[|\\]", "");
			sb.append(password).append("\n");
			return;
		}
		
		for(int i = index ; i < size ; i++) {
			String alph = alphabet.get(i);
			
			if("aeiou".contains(alph)) {
				cnt_consonant++;
			}
			else {
				cnt_vowel++;
			}
			
			result.add(alph);
			combination(alphabet, result, size, r - 1, i + 1, cnt_consonant, cnt_vowel);
			result.remove(result.size() - 1);
			
			if("aeiou".contains(alph)) {
				cnt_consonant--;
			}
			else {
				cnt_vowel--;
			}
		}
	}
	
}