백준 1759. 암호 만들기 (백트래킹으로 다시 풀어보기)

www.acmicpc.net/problem/1759

1759번: 암호 만들기

문제제목 : 암호 만들기

문제유형 : 브루트포스, 조합, 백트래킹 (해결 방법을 얻을 때까지 모든 가능성을 확인해서 찾는 방법)

문제난이도 : 골드 5

문제

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

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

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

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

접근방식

0. 암호는 L개의 알파벳 소문자
1. 최소 1개의 a,e,i,o,u 
2. 최소 2개의 자음 
3. 오름차순. abc OK, bac X
4. C 가지 종류 사용 가능

 

암호의 알파벳은 오름차순이므로 오름차순으로 정렬을 해준다.

C종류의 문자 중 L개를 뽑아서 나온 문자의 자음과 모음 개수를 세어 조건에 맞으면 출력하도록 하였다.

C개 중 L개를 뽑는 것은 "재귀를 이용한 조합"을 이용하였다. 

코드 (재귀)

package week6;

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

public class BOJ1759 {
	public static StringBuffer sb = new StringBuffer();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] input = br.readLine().split(" ");
		int L = Integer.parseInt(input[0]);
		int C = Integer.parseInt(input[1]);
		
		// 문자
		String[] letter = new String[C];
		input = br.readLine().split(" ");
		for (int i = 0; i < C; i++) {
			letter[i] = input[i];
		}
		
		Arrays.sort(letter); // 오름차순 정렬
		String[] str = new String[L];
		pick(letter, str, L, L, 0);
		
		System.out.print(sb.toString());
	}
	// 뽑기
	public static void pick(String[] letter, String[] bucket, int bucketSize, int k, int index) {
		if (k == 0) { //c개의 문자를 조합했으므로, 자음모음개수 확인
			int con = 0; //자음
			int vo = 0; //모음

			for (int i = 0; i < bucketSize; i++) {
				if (bucket[i].equals("a")  || bucket[i].equals("e") 
						|| bucket[i].equals("i")  || bucket[i].equals("o") || bucket[i].equals("u")) {
					vo++; //모음이면 모음 개수++
				} else {
					con++; //자음이면 자음 개수++
				}
			}
			
			if (con >= 2 && vo >= 1) {
				for (int i = 0; i < bucketSize; i++) {
					sb.append(bucket[i]);
				}
				sb.append("\n");
			}
			return;
		}
		
		int lastIndex = bucketSize - k - 1; // 현재 선택한 문자 개수 (버켓 크기)
		int smallest = 0;
		// 문자를 하나도 선택하지 않은 경우
		if(bucketSize == k) {
			smallest = 0; 
		} else {
			smallest = index + 1; // index : bucket에 담은 letter의 마지막 인덱스번호
		}
		
		for (int i = smallest; i < letter.length; i++) {
			bucket[lastIndex + 1] = letter[i];
			pick(letter, bucket, bucketSize, k - 1, i);
		}
	}
}

 

 

문제를 읽고 문해기 강의때 들은 순열, 조합 코드를 배웠던 것이 생각나서 복습 후 재귀를 이용한 조합을 이용해서 풀이하였다.

다른 사람들의 답을 보니 백트래킹(BFS사용) 알고리즘을 이용해서 풀이를 하던데, 백트래킹 알고리즘을 공부한 후 조만간 다시 풀어볼 것이다.