[백준] 가르침 (1062)(kotlin)

문제 설명

백준 1062번 문제 링크

입력 및 출력

» 입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

» 출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

예제 입출력(테스트케이스)

입력	출력
3 6 antarctica antahellotica antacartica	2
2 3 antaxxxxxxxtica antarctica	0
9 8 antabtica antaxtica antadtica antaetica antaftica antagtica antahtica antajtica antaktica	3
1 7 antabbtica	1
2 7 antaatica antabtica	2
1 7 antabctica	1

문제 풀이1(실패 - 메모리 초과)

import kotlin.math.max

var k = 0
var n = 0
val visited: IntArray = IntArray(26) { 0 }
val list: MutableList<BooleanArray> = mutableListOf()
val must: CharArray = charArrayOf('a', 'c', 'i', 'n', 't')

fun main() = with(System.`in`.bufferedReader()) {
    readLine()
        .split(" ")
        .run {
            n = this[0].toInt()
            k = this[1].toInt()

            if (k < 5) {
                // k < 5, 어떠한 단어도 읽을 수 없음, k == ('a', 'c', 'i', 'n', 't')
                println(0)
                return
            }
            else if (k == 26) {
                // k == 26, 모든 알파뱃을 읽을 수 있음, 'a' ~ 'z' == 26개
                println(n)
                return
            }
        }

    var words: Array<BooleanArray> = Array(n) { BooleanArray(26) { false } }

    repeat(n) {
        var str = readLine()
        str = str.substring(4..str.length - 5)

        for (char in str) {
            visited[char - 'a']++
            words[it][char - 'a'] = true
        }

        for (char in must) {
            words[it][char - 'a'] = true
        }
    }

    for (i in 0 until 26) {
        if (visited[i] != 0) {
            val bArray = bArrayInit()
            visited[i]--
            bArray[i] = true
            dfs(bArray, i, 1)
//            visited[i]++
        }
    }

    list.forEach {
        print(it.count { bool -> bool })
        println(it.contentToString())
    }

    var answer: Int = 0
    for (case in list) {
        answer = max(
            words.filter { booleans ->
            var bool = true
            for (i in 0 until 26) {
                if (!case[i] && booleans[i]) {
                    bool = false
                    break
                }
            }
            bool
        }.size, answer)
    }

    println(answer)
}

fun dfs(bArray: BooleanArray, start: Int, count: Int) {
    if (count == k - 5) {
        list.add(bArray.copyOf())
        return
    }

    for (i in start until 26) {
        if (visited[i] != 0) {
            bArray[i] = true
            visited[i]--
            dfs(bArray, i, count + 1)
            bArray[i] = false
            visited[i]++
        }
    }
}

fun bArrayInit(): BooleanArray {
    val bArray = BooleanArray(26) { false }
    for (char in must) {
        bArray[char - 'a'] = true
    }
    return bArray
}