[백준] 1759번 암호 만들기(깊이우선탐색 - DFS)[Kotlin - 코틀린]

백준 1759번 문제입니다. (solved.ac) 기준 골드 5 문제입니다.

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

1759번: 암호 만들기

문제

문제 접근

첫 번재 줄에 두 정수 l, c가 주어지고 두 번째 줄에는 c개의 알파벳이 주어집니다.

암호의 후보는 주어진 c개의 알파벳중에서 l개로 이루어진 문자들이 사전순으로 정렬되어있는 문자열 입니다.

또한 최소 한 개의 모음(a,e,i,o,u)와 두 개의 자음으로 구성이 되어야합니다.

c개의 알파벳들 중 암호의 후보들을 사전순으로 정렬해서 출력하면 되는 문제입니다.

 

우선 암호는 사전순으로 정렬이 되어있어야 하므로 알파벳 c개를 입력받을 때 리스트로 만들고 정렬을 해줍니다.

정렬을 한 c개의 알파벳에서 l개를 뽑는 조합을 구한 후(문자열) 해당 문자열이 한 개 이상의 모음을 포함하고 있고 두 개 이상의 자음을 포함하고 있다면 암호의 후보이므로 정답리스트에 입력해줍니다.

 

암호의 후보들이 모인 정답리스트를 정렬 후 한 줄에 하나씩 출력해주면 됩니다.

정답 코드

lateinit var alphabets: List<String>
lateinit var visited: BooleanArray
val pickedAlphabets = mutableListOf<String>()
val ansList = mutableListOf<String>()

fun main() {

    val (l, c) = readln().split(" ").map { it.toInt() }
    visited = BooleanArray(c, { false })

    // 아예 사전순 정렬해버리기.
    alphabets = readln().split(" ").sorted()

    findCrypto(0, l, 0)
    ansList.sorted().forEach {
        println(it)
    }

}

fun findCrypto(cnt: Int, depth: Int, beginWith: Int) {
    if (cnt == depth) {
        // 가능성이 있는 암호가 되려면
        // 모음이 하나 이상, 자음이 두개이상이어야함.
        var vowelsCnt = 0
        var consonantsCnt = 0

        pickedAlphabets.forEachIndexed { index, it ->
            if (isVowels(it)) vowelsCnt++
            else consonantsCnt++
        }

        if (vowelsCnt >= 1 && consonantsCnt >= 2) ansList.add(pickedAlphabets.joinToString(""))

    }
    for (index in beginWith until visited.size) {
        pickedAlphabets.add(alphabets[index])
        findCrypto(cnt + 1, depth, index + 1)
        pickedAlphabets.removeAt(pickedAlphabets.lastIndex)
    }
}

// 모음인가?
fun isVowels(alphabet: String): Boolean {
    var isVowels = false
    when (alphabet) {
        "a", "e", "i", "o", "u" -> isVowels = true
    }
    return isVowels
}