[알고리즘] 암호 만들기 (백준 1759번)

1759번: 암호 만들기

 브루트 포스 문제이며 상당히 자주 볼 수 있는 문제의 유형이다. (물론 난이도가 낮아서 코딩 테스트에선 자주 안 나올 것 같다)

 만들 수 있는 조합의 문자열을 DFS를 통한 완전탐색으로 찾아내는 케이스이다. 조합으로 계산해봤을 때 C가 맥스인 15가 되더라도 문자 하나가 정해지면 그 뒤에 올 수 있는 문자들의 범위는 계속해서 줄어들게 되기 때문에 시간복잡도가 크게 증가하지 않는다.

 

Solution

1. 입력받은 알파벳들을 사전식으로 오름차순 정렬한다.
2. L글자를 구성가능한 index까지만 dfs를 돌린다. EX) a t c i s w에 L이 4라면 a, t, c 까지만 첫 문자로 삽입이 가능하다.
   1. 아직 문자열이 L글자가 아니면 붙일 수 있는 조합을 더 만든다.
   2. 문자열이 L글자가 되면 자음 개수 2개, 모음 개수 1개인지 파악 후 result에 추가한다.
3. result 출력

import kotlin.collections.ArrayList

var L = 0
var C = 0
lateinit var alphabets : CharArray
var vowels = setOf('a','e','i','o','u')
var result = ArrayList<String>()

fun solution() {

    readLine()!!.split(" ").forEachIndexed { index, s -> if(index == 0) L = s.toInt() else C = s.toInt() }

    alphabets = CharArray(C)
    readLine()!!.split(" ").forEachIndexed { index, s ->
        alphabets[index] = s[0]
    }

    //사전식 오름차순 정렬
    alphabets.sort()

    //L글자만큼 구성이 가능한 시작점만 DFS
    alphabets.forEachIndexed{index, c -> if(index <= C - L) dfs("$c", index + 1) }

    result.forEach{ println(it)}
}

fun dfs(current : String, index : Int)
{
    var current = current

    if(current.length == L)
    {
        var current_char = current.toCharArray()
        var vowel_count = current_char.count { c -> c in vowels }//모음 개수
        var consonant_count = current_char.count { c -> c !in vowels } //자음 개수

        if(vowel_count >= 1 && consonant_count >= 2)
            result.add(current)
    }
    else
    {
        for(i in index until C)
        {
            dfs(current + alphabets[i], i + 1)
        }
    }

}


fun main() {
    solution()
}