[ 백준 ] 1759 암호 만들기

📌 Problem

주어진 C개의 문자들에서 L개의 문자를 골라서 만들 수 있는 모든 암호를 출력하면 된다. 이 때 암호는 최소 1개의 모음과 2개의 자음을 가지고 있어야 하며 정렬된 상태여야 한다. 모든 암호들의 출력 순서 또한 정렬된 상태이다.

📌 Solution

백트래킹으로 해결할 수 있는 문제이다. 우선 암호는 정렬된 상태여야 하고 출력되는 암호들도 정렬된 상태여야 한다. 그렇기 때문에 입력된 문자들을 우선 정렬한다.

char[] chars = reader.readLine().replaceAll(" ", "").toCharArray();
Arrays.sort(chars);

모음을 구별하기 위한 Set과 암호를 저장할 Stack 자료구조도 만들어준다.

final Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
Stack<Character> password = new Stack<>();

탐색을 할 때 문자들을 순서대로 탐색하기 때문에 어느 문자(인덱스)부터 탐색하는지에 대한 정보가 필요하다. 또한 현재까지 모음이 몇 개 포함되었는지에 대한 정보도 필요하다.

private void search(int index, int vowelNum) {
	// 백트래킹 탐색
}

탐색을 하다가 암호의 크기가 L과 같아지면 출력을 한다. 이 때 모음과 자음의 개수를 확인하여 가능한 암호인지 확인한다.

private void search(int index, int vowelNum) {
    if (password.size() == LEN) {
        if (vowelNum >= 1 && LEN - vowelNum >= 2)
            result.append(password.stream().map(String::valueOf).collect(Collectors.joining()))
                    .append("\n");
    } else {
    	// 백트래킹
    }
}

백트래킹을 할 때는 index부터 탐색을 한다. index에 해당하는 문자를 password에 삽입하고 다음 탐색을 한다. 다음 탐색을 할 때는 모음인지를 판단하여 모음의 개수를 업데이트한다. 다음 탐색이 마무리 되었을 때는 현재 삽입한 문자를 제거한다.

private void search(int index, int vowelNum) {
    if (password.size() == LEN) {
        if (vowelNum >= 1 && LEN - vowelNum >= 2)
            result.append(password.stream().map(String::valueOf).collect(Collectors.joining()))
                    .append("\n");
    } else for (int i = index; i < chars.length; i++) {
        password.push(chars[i]);
        search(i + 1, vowels.contains(chars[i]) ? vowelNum + 1 : vowelNum);
        password.pop();
    }
}

📌 Code

final Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');

int LEN;
char[] chars;
Stack<Character> password = new Stack<>();

public void solve() throws IOException {
    init();
    search(0, 0);
}

private void search(int index, int vowelNum) {
    if (password.size() == LEN) {
        if (vowelNum >= 1 && LEN - vowelNum >= 2)
            result.append(password.stream().map(String::valueOf).collect(Collectors.joining()))
                    .append("\n");
    } else for (int i = index; i < chars.length; i++) {
        password.push(chars[i]);
        search(i + 1, vowels.contains(chars[i]) ? vowelNum + 1 : vowelNum);
        password.pop();
    }
}

private void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    LEN = Integer.parseInt(tokenizer.nextToken());
    int charNum = Integer.parseInt(tokenizer.nextToken());
    chars = reader.readLine().replaceAll(" ", "").toCharArray();
    Arrays.sort(chars);
}