백준 1759 암호 만들기

https://www.acmicpc.net/problem/1759

주어진 알파벳들로 길이 L의 오름차순이고, 한 개 이상의 모음과 두 개 이상의 자음으로 구성된 암호들을 출력하는 문제이다.

L과 C 모두 3~15 사이의 정수이므로, C개중에 L개를 뽑는 조합을 구하되 dfs에서 자음과 모음 개수를 전달해줌으로써 조건에 대한 필터링을 해주기로 했다.

가장 많은 케이스라 해도 15C7 (15개중에 7개를 뽑는 조합) 이므로 시간 안에 해결할 수 있다고 생각했다.

dfs의 파라미터로 생각한 것들은 아래와 같다.

1. conso: 현재 고른 알파벳들 중 자음의 개수이다

2. cap: 현재 고른 알파벳들 중 모음의 개수이다

3. start: 조합의 구현을 위해 다음 뽑을 위치를 나타내는 변수이다

4. target: 남은 뽑기 개수를 나타내는 변수이다.

5. ck: 고른 알파벳에 대한 체크를 담당하는 배열이다.

이를 토대로 작성한 코드이다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (L, C) = readLine().split(' ').map{it.toInt()}
    val chars = readLine().split(' ').map{it[0]}

    val cases = mutableListOf<String>()
    val answer = StringBuilder()

    fun dfs(conso: Int, cap: Int, start: Int, target: Int, ck: BooleanArray){
        if(target == 0){
            if(conso >= 2 && cap >= 1){
                cases.add(chars.filterIndexed { index, c -> ck[index] }.sorted().joinToString(separator = ""))
            }
        }else {
            for (i in start until C) {
                ck[i] = true
                if ("aeiou".contains(chars[i])) {
                    dfs(conso, cap + 1, i + 1, target - 1, ck)
                } else {
                    dfs(conso + 1, cap, i + 1, target - 1, ck)
                }
                ck[i] = false
            }
        }
    }

    dfs(0, 0, 0,L, BooleanArray(chars.size){false})

    for(str in cases.sorted()){
        answer.append("$str\n")
    }
    print(answer.toString())
}

target이 0인 경우 (원하는 개수 L개만큼 뽑은 경우), 자음과 모음 개수를 체크한 후 정렬한 뒤 정답 케이스에 추가했다.

재귀 부분은 현재 위치의 알파벳이 모음인 경우(aeiou에 포함되면) cap을 1 증가시켜 재귀하고 자음인 경우 conso를 1 증가시켜 재귀하였다.