[백준 5446번] 파이썬 - 용량 부족

백준 5446 - 용량 부족

시간 제한 1초, 메모리 제한 128MB

# 조건

• 팀포2 덕후 연수는 팀포2를 다운받던 도중 하드 용량이 부족하다는 것을 알았다.
• 이때는 침착하게 팀포2를 하지 말거나 하드를 새로 사면 되지만 불가능했고, 결국 하드에서 쓸모없는 파일을 지워야만 한다.
• 연수는 또한 턱스 덕후여서 리눅스를 사용중이다.
• 리눅스에서 현재 디렉토리의 특정 파일을 지우려면 "rm 파일명"의 형식을 갖춰 명령하면 된다.
• 그러나 파일 개수가 너무 많을 경우 일일이 다 칠 수 없기에, 와일드카드 ' * '를 사용할 수도 있다.
• "rm 문자열*" 형식으로 명령하면 현재 디렉토리에서 파일 이름이 "문자열"이거나 "문자열"로 시작하는 모든 파일이 한번에 삭제된다!
• 그러나 지워서는 안 되는 파일들 또한 존재한다.
• rm 명령어를 잘못 사용하여 이러한 파일들을 지우지 않도록 조심해야 할 것이다. 때에 따라서 "rm * "도 사용할 수 있긴 하다.
• 현재 디렉토리의 모든 파일을 지우고 싶을 때만...
• 모든 파일이 디렉토리 하나에 존재하고 연수가 그 디렉토리에 있을 때, 지우고 싶은 파일들을 모두 지우는 데 필요한 최소 rm 명령 횟수를 구하시오.
• 단, 사용할 수 있는 와일드카드는 ' * ' 뿐이며 반드시 제일 끝에만 사용해야 한다.
  • 예를 들면 "rm * .txt"는 사용할 수 없다.

입력

• 입력은 여러 개의 테스트 케이스로 주어지며,
• 첫째 줄에 테스트 케이스의 개수가 주어진다.
• 각 테스트 케이스는 다음과 같은 형식이다.
  • 첫째 줄에 지워야 하는 파일의 개수 N1이 주어진다. (1 ≤ N1 ≤ 1000)
  • 이어서 N1개의 줄에 지워야 하는 파일명이 줄마다 하나씩 주어진다.
  • 이어서 지우면 안 되는 파일의 개수 N2가 주어진다. (0 ≤ N2 ≤ 1000)
  • 이어서 N2개의 줄에 지우면 안 되는 파일명이 줄마다 하나씩 주어진다.
• 파일 이름은 모두 1글자 이상 20글자 이하이며, 영문 대소문자, 숫자, 점(.)으로만 이루어져 있다.
• 하나의 테스트 케이스에 등장하는 모든 파일 이름은 서로 다르다.

출력

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

# 접근 방법

• 문자열을 효율적으로 탐색해야 하므로 Trie를 만들어 사용해주었다.
• 지워야되는 문자열과 지우면 안되는 문자열을 입력받은 후 지우면 안되는 문자들을 순회한다.
  • 각 단어가 현재 node에 없다면 생성 후 1 depth 들어가주고, 존재한다면 그 node로 이동해준다.
  • 즉 red라는 문자가 있을 때 {} 비어있는 상태에서 {r : {}} 를 생성해주고 now = now[r]로 변경해준다.
  • r : {} 에는 e가 존재 하지 않으므로 {r : {e : {}}}로 생성해주고 위의 단계를 반복하면 {r : {e : {d: {end : {}}}}}가 되는 것이다.
• 트라이를 생성했다면 지워야 되는 단어를 순회하며 check 함수를 실행해준다.
• 트라이 생성시와 마찬가지로 한 알파벳씩 확인하며
  • 현재 end가 아니고 => trie에 저장된 마지막 글자가 아니고, trie에 존재하는 문자열이라면 now = now[w]로 변경하며 계속 확인해준다.
  • 만약, 존재하지 않거나 현재 단어가 끝나지 않았는데 end를 만났다면 wildcard 세트에 지금까지의 문자열 + trie에 존재하지 않는 문자열을 저장해준다.
    • cleanup이 존재하고 현재 순회중인 문자열이 cleaning이라면 i를 확인할 때 존재하지 않는 것을 확인한다.
    • 따라서 wildcard 세트에 cleani* 로 저장해준다.
  • 또한, 확인하는 반복문이 끝났다면 => 현재 문자열이 trie에 존재하지만 'end'를 만나지 않았다면, 단어 그 자체를 wildcard에 저장해준다.
    • 예를 들면, cleanup이 trie에 존재하지만 clean은 삭제해야되는 문자열이므로 wildcard에는 clean이 들어간다.
• 여기서 조심해야 될 점은 삭제해야될 문자열이 A, B로 들어오고 삭제하면 안되는 문자열이 없는 경우 * 하나로 모두 삭제가능하지만
  • 현재 로직은 A, B 로 저장되기 때문에 출력시 삭제하면 안되는 문자열이 0개인 경우 1을 출력해주어야 한다.

import sys  
sys.stdin = open('input.txt')  
si = sys.stdin.readline  

def check(word):  
    now = no_remove  
    temp = ''  
    for w in word:  
        if not now == 'end' and w in now:  
            now = now[w]  
            temp += w  
        else:  
            temp += w  
            wildcard.add(f'{temp}*')  
            return  

    wildcard.add(f'{temp}')  
T = int(si())  
for _ in range(T):  
    N = int(si())  
    remove = [si().strip() for _ in range(N)]  
    M = int(si())  
    words = [si().strip() for _ in range(M)]  
    no_remove = dict()  
    for i in words:  
        now = no_remove  
        for j in i:  
            if not j in now:  
                now[j] = {}  

            now = now[j]  

        now['end'] = {}  
    wildcard = set()  
    for i in remove:  
        check(i)  
    if M == 0:  
        print(1)  
    else:  
        print(len(wildcard))