백준 1759번
https://www.acmicpc.net/problem/1759

문제

---

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

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

생각하기

---

백트래킹을 사용한 조합론 문제였는데, 문제자체는 그렇게 어렵지 않았지만, 마지막 출력 부분에서 자꾸 메모리초과가 나와서 조금 해멨던 문제였다.

동작

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<C; i++) {
			arr[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(arr);

먼저 문제에서 말한 조건중 알파벳이 증가하는 순서라고 했기 때문에 문자형 배열을 만들고 정렬을 해준다.

		for(int i=index; i<C; i++) {
	
			if(visit[i]) continue;

			// 자기 보다 낮은 숫자에 false가 있으면 지나쳐야함.
			visit[i] = true;
			DFS(i + 1, depth + 1, str + arr[i]);
			visit[i] = false;
		}

다음은 백트래킹에서 증가하는 순서이므로 지나친 문자에는 다시 돌아가지 않기 위해서 반복문 i의 값을 index를 기점으로 시작하게 만들어준다.

	static boolean check(String str) {
		// 최소 한개의 모음 2개의 자음 체크

		char ch[] = str.toCharArray();
		int len = ch.length;
		int count = 0;
		int count2 = 0;
		for(int i=0; i<len; i++) {

			if(ch[i] == 'a' || ch[i] == 'e' || ch[i] == 'i' || ch[i] == 'o' || ch[i] == 'u') {
				count++;
			}
			else {
				count2++;
			}
		}

		if(count > 0 && count2 >= 2) {
			return true;
		}


		return false;
	} // End of check

check 메소드에서는 모음과 자음의 개수를 파악해서 만들어진 문자조합이 암호의 조건에 부합하는지 파악한다.

이 3가지의 경우를 파악한다면 문제는 쉽게 해결이 가능하다.

코드

---

Java

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

public class Main {
	static char arr[];
	static boolean visit[];
	static int L, C;
	static String result = "";

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine());
		L = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		arr = new char[C];
		visit = new boolean[C];

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<C; i++) {
			arr[i] = st.nextToken().charAt(0);
		}
		Arrays.sort(arr);

		DFS(0, 0, "");

		System.out.println(result);
	} // End of main

	static void DFS(int index, int depth, String str) {
		if(depth == L) {

			if(check(str)) {				
				result += str + "\n";
				return;
			}

			return;
		}

		for(int i=index; i<C; i++) {
	
			if(visit[i]) continue;

			// 자기 보다 낮은 숫자에 false가 있으면 지나쳐야함.
			visit[i] = true;
			DFS(i + 1, depth + 1, str + arr[i]);
			visit[i] = false;
		}

	} // End of DFS

	static boolean check(String str) {
		// 최소 한개의 모음 2개의 자음 체크

		char ch[] = str.toCharArray();
		int len = ch.length;
		int count = 0;
		int count2 = 0;
		for(int i=0; i<len; i++) {

			if(ch[i] == 'a' || ch[i] == 'e' || ch[i] == 'i' || ch[i] == 'o' || ch[i] == 'u') {
				count++;
			}
			else {
				count2++;
			}
		}

		if(count > 0 && count2 >= 2) {
			return true;
		}


		return false;
	} // End of check

} // End of Main class

Kotlin

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

fun main() {
    val br = BufferedReader( InputStreamReader(System.`in`) )
    var st = StringTokenizer(br.readLine());
    var sb = StringBuilder()
    var L = st.nextToken().toInt();
    var C = st.nextToken().toInt();
    var arr = Array(C, {' '});
    var visit = Array(C, {false});

    st = StringTokenizer(br.readLine());
    for(i in 0..C-1) {
        arr[i] = st.nextToken()[0];
    }
    Arrays.sort(arr)

    fun check(str : String) : Boolean {
        var ch = str.toCharArray()
        val len = ch.size;
        var count = 0;
        var count2 = 0;

        for(i in 0..len-1) {

            if(ch[i] == 'a' || ch[i] == 'e' || ch[i] == 'i' || ch[i] == 'o' || ch[i] == 'u') {
                count++;
            }
            else {
                count2++;
            }
        }

        if(count > 0 && count2 >=2 ) {
            return true;
        }

        return false;
    } // End of check

    fun DFS(index : Int, depth : Int, str : String) {

        if(depth == L) {
            if(check(str)) {
                sb.append(str).append('\n')
                return;
            }
            return;
        }

        for(i in index..C-1) {

            if(visit[i]) continue;

            visit[i] = true;
            DFS(i+1, depth+1, str+arr[i]);
            visit[i] = false;
        }
    } // End of DFS

    DFS(0, 0, "");
    println(sb);

} // End of main