백준/문제

5446번: 용량 부족

스몰스테핑 2024. 9. 5. 14:24

문제 출처 : https://www.acmicpc.net/problem/5446

 

언어 : Kotlin

 

문제 설명 :

팀포2 덕후 연수는 팀포2를 다운받던 도중 하드 용량이 부족하다는 것을 알았다. 이때는 침착하게 팀포2를 하지 말거나 하드를 새로 사면 되지만 불가능했고, 결국 하드에서 쓸모없는 파일을 지워야만 한다.

연수는 또한 턱스 덕후여서 리눅스를 사용중이다. 리눅스에서 현재 디렉토리의 특정 파일을 지우려면 "rm 파일명"의 형식을 갖춰 명령하면 된다. 그러나 파일 개수가 너무 많을 경우 일일이 다 칠 수 없기에, 와일드카드 '*'를 사용할 수도 있다. "rm 문자열*" 형식으로 명령하면 현재 디렉토리에서 파일 이름이 "문자열"이거나 "문자열"로 시작하는 모든 파일이 한번에 삭제된다! 그러나 지워서는 안 되는 파일들 또한 존재한다. rm 명령어를 잘못 사용하여 이러한 파일들을 지우지 않도록 조심해야 할 것이다. 때에 따라서 "rm *"도 사용할 수 있긴 하다. 현재 디렉토리의 모든 파일을 지우고 싶을 때만...

모든 파일이 디렉토리 하나에 존재하고 연수가 그 디렉토리에 있을 때, 지우고 싶은 파일들을 모두 지우는 데 필요한 최소 rm 명령 횟수를 구하시오. 단, 사용할 수 있는 와일드카드는 '*' 뿐이며 반드시 제일 끝에만 사용해야 한다. 예를 들면 "rm *.txt"는 사용할 수 없다.

 

입력 :

입력은 여러 개의 테스트 케이스로 주어지며, 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.

  • 첫째 줄에 지워야 하는 파일의 개수 N1이 주어진다. (1 ≤ N1 ≤ 1000)
  • 이어서 N1개의 줄에 지워야 하는 파일명이 줄마다 하나씩 주어진다.
  • 이어서 지우면 안 되는 파일의 개수 N2가 주어진다. (0 ≤ N2 ≤ 1000)
  • 이어서 N2개의 줄에 지우면 안 되는 파일명이 줄마다 하나씩 주어진다.

파일 이름은 모두 1글자 이상 20글자 이하이며, 영문 대소문자, 숫자, 점(.)으로만 이루어져 있다. 하나의 테스트 케이스에 등장하는 모든 파일 이름은 서로 다르다.

 

출력 :

각 테스트 케이스마다 한 줄에 걸쳐 문제의 정답을 출력한다.

 

제한 사항 :

  • 시간 제한 : 1초
  • 메모리 제한 : 128MB

 

입출력 예 :

입력 출력
1
11
BAPC.in
BAPC.out
BAPC.tex
filter
filename
filenames
clean
cleanup.IN1
cleanup.IN2
cleanup.out
problem.tex
5
BAPC
files
cleanup
cleanup.IN
cleaning		 8

 

풀이 : 

트라이 구조를 사용한 문제.

트라이를 사용하며 문자열 삽입, 삭제할 문자열 끝, 삭제할 문자인지, 아닌지를 체크하며 삽입. (insert 함수)

경우의 수에 따라 어떻게 지울지를 생각해야한다. (find 함수)

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    repeat(readLine().toInt()) {
        val trie = Trie()

        val n1 = readLine().toInt()
        repeat(n1) {
            val cur = readLine()
            trie.insert(cur, false)
        }

        val n2 = readLine().toInt()
        repeat(n2) {
            val cur = readLine()
            trie.insert(cur, true)
        }

        bw.write(if (n2 > 0) "${trie.find()}\n" else "1\n")
    }

    bw.flush()
    bw.close()
}

class TrieNode {
    val children = mutableMapOf<Char, TrieNode>()
    var doNotDelete = false
    var doDelete = false
    var doDeleteEnd = false
}

class Trie(private val root: TrieNode = TrieNode()) {
    fun insert(s: String, flag: Boolean) {
        var cur = root

        for (i in s.indices) {
            val c = s[i]
            if (!cur.children.containsKey(c)) cur.children[c] = TrieNode()

            cur = cur.children[c]!!

            if (flag) cur.doNotDelete = true else cur.doDelete = true
            if (!flag && i == s.length - 1) cur.doDeleteEnd = true
        }
    }

    fun find(): Int {
        return find(root)
    }

    private fun find(node: TrieNode): Int {
        var cmds = 0
        for ((_, cur) in node.children) {
            if (cur.doDelete) {
                if (!cur.doNotDelete) cmds++
                if (cur.doDeleteEnd && cur.doNotDelete) cmds++
                if (cur.doNotDelete) cmds += find(cur)
            }
        }

        return cmds
    }
}