문제풀이
- trie 자료 구조를 구현하고, 하위 항목에 삭제할 파일이 있는지, 하위 항목에 삭제하면 안되는 파일이 있는지, 현재 파일이 삭제해야 되는 파일인지 여부를 체크한다.
- trie를 순회하며 삭제 횟수를 구한다.
주의사항
소요시간
35분
package 백준.Platinum.P3.p5446_용량부족
class Trie(val idx: Int) {
private val children = mutableMapOf<Char, Trie>()
private var hasDeleteFile = false
private var needToDelete = false
private var canDelete = true
fun addDeleteFile(str: String) {
hasDeleteFile = true
if (str.length == idx) {
needToDelete = true
return
}
getChild(str[idx]).addDeleteFile(str)
}
fun addCanNotDeleteFile(str: String) {
canDelete = false
if (str.length == idx) return
getChild(str[idx]).addCanNotDeleteFile(str)
}
private fun getChild(c: Char): Trie {
if (c !in children) children[c] = Trie(idx + 1)
return children[c]!!
}
fun count(): Int {
if (!hasDeleteFile) return 0
if (canDelete) return 1
var count = if (needToDelete) 1 else 0
for ((_, child) in children) {
count += child.count()
}
return count
}
}
fun main() {
val sb = StringBuilder()
repeat(readln().toInt()) {
val trie = Trie(0)
repeat(readln().toInt()) { trie.addDeleteFile(readln()) }
repeat(readln().toInt()) { trie.addCanNotDeleteFile(readln()) }
sb.appendLine(trie.count())
}
println(sb)
}