[백준 1062] - 가르침(Kotlin)[골드4]

문제

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

1062번: 가르침

문제 풀이

최적화에 신경 쓰지 않는다면 엄청난 시간초과를 맛볼 수 있는 문제이다.

최대한 경우의 수를 줄여서 최소한의 탐색으로 해결해야 한다.

학생들은 K개의 글자를 배우고, K개의 글자로 이루어진 단어만 읽을 수 있다.

즉 우리는 N개의 단어 중에서 K개의 글자를 골라서 주어진 N개의 단어들 중에서 최대한 많이 읽어야 한다.

문제에서는 친절하게 반드시 배워야 할 글자들을 제시해 준다.

"a", "n", "c", "t", "i" -> 해당 글자들은 모든 단어에서 등장하는 글자들이다.

위 단서를 가지고 우리는 K개의 글자를 골라야 할 것이다.

 

탐색을 하기 전에 입력에서 경우의 수를 최대한 줄일 수 있다.

• K가 26일 경우
  • 알파벳의 글자수는 26이다. 따라서 K가 26일 경우 모든 단어를 읽을 수 있을 것이다.
• K가 5 미만인 경우
  • 모든 단어들은 a, c, i, n, t를 가진다. 따라서 k가 5 미만일 경우 읽을 수 있는 단어의 개수는 없을 것이다.

 

나는 Set이라는 자료 구조를 이용했고, 그중에서 hashSet을 사용했다.

두 가지의 Set을 사용했는데,

• 내가 배운 알파벳
• 아직 배우지 않은 알파벳(a~z - [a, n, t, c, i])

탐색을 시작하기 전에 내가 베운 알파벳에 a, n, c, t, i를 추가해 준다.

그리고 전체 알파벳 조합에서 a, n, c, t, i를 빼준다.

다음은 dfs를 통해서 k개의 글자를 배운다면, 몇 개를 읽을 수 있는지 계속해서 업데이트해 준다.

몇 개를 읽을 수 있는지 체크하는 과정은 단어들을 문자열로 받아오고, 해당 단어에서 내가 배운 알파벳들이 포함되어 있는지 아닌지를 판단한다.

 

나는 set을 사용했지만, 문제의 핵심은 얼마나 많은 경우의 수를 사전에 제거해서 최소한의 탐색을 하느냐라고 생각한다.

 

 

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.HashSet
import kotlin.math.max

private var n = 0
private var k = 0
private val br = BufferedReader(InputStreamReader(System.`in`))
private var words: MutableList<String> = mutableListOf()
private var result = 0
private var alpha: HashSet<Char> = hashSetOf()
private var total: HashSet<Char> = hashSetOf()
fun main() {
    initAlpha()
    if (input()) {
        combination(5, k, 0)
        println(result)
    } else {
        println(result)
    }
}

fun input(): Boolean {
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    k = st.nextToken().toInt()
    if (k < 5) {
        result = 0
        return false
    } else if (k == 26) {
        result = n
        return false
    }
    for (i in 0 until n) {
        words.add(br.readLine())
    }
    return true
}

fun initAlpha() {
    with(alpha) {
        add('a')
        add('c')
        add('n')
        add('t')
        add('i')
    }
    with(total) {
        for (char in 'a'..'z') {
            add(char)
        }
        removeAll(alpha)
    }
}

fun combination(cnt: Int, limit: Int, loc: Int) {
    if (cnt == limit) {
        solution()
        return
    }
    for (i in loc until total.size) {
            alpha.add(total.elementAt(i))
            combination(cnt + 1, limit, i + 1)
            alpha.remove(total.elementAt(i))
    }
}

fun solution() {
    var answer = 0
    for (word in words) {
        var isValid = true
        for (char in word) {
            if (!alpha.contains(char)) {
                isValid = false
                break
            }
        }
        if (isValid)
            answer++
    }
    result = max(result, answer)
}