백준 - [Platinum 3] 5446번 용량 부족

문제링크: https://www.acmicpc.net/problem/5446

5446번: 용량 부족

---

문제 설명

- N1: 지워야 할 파일의 개수

- N1개의 파일명이 주어짐

- N2: 지우지 말아야 할 파일의 개수

- N2개의 파일명이 주어짐

rm * 명령어로 전체 삭제도 가능합니다. rm a*이면 a로 시작하는 파일명들을 전부 삭제하는 명령어입니다.

지워야하는 파일만 지우게 할 수 있는 최소의 명령어 개수를 구하는 문제입니다.

 

ex)

N1=4 N2=1

N1: BAP, BAPC.in, BAPC.out, BAPC.tex

N2: BAPC

이면 rm BAP*를 하면 BAPC도 지워지므로 안됩니다.

rm BAP 와 rm BAPC.* 명령어 2개의 명령어가 최소의 개수입니다.

 

---

풀이

Trie 자료구조를 활용한 문제입니다.

트라이는 위의 사진과 같이 각 캐릭터를 하나의 노드에 두어 중복된 문자열을 최소화하며 트리구조로 만들어 나가는 자료구조입니다.

 

이 문제에서는 어떻게 활용해야 하는지 설명드리겠습니다.

1. 지워야 할 파일들을 trie로 만들어 줍니다.

2. 지우지 말아야 할 파일들을 trie 내에서 삭제하지 말라는 marking을 해줍니다. (mark = 1)

3. 지워야 할 파일들을 루프를 돌며 삭제 가능한지 판단합니다. 여기서 중요한 점이 있습니다.

• rm BAPC.* 으로 삭제를 했을경우 BAPC.in BAPC.out를 한 명령어로 처리해주어야 합니다.
• 그래서 '.'인 지점에 mark를 2로 변경하여 BAPC.out파일명이 왔을때 바로 리턴하도록 해주어야 합니다.

주의할 점

• mark나 remove할 때 꼭 끝 지점도 체크를 해주어야 합니다.
• N2가 0일때를 따로 처리해 주어야 합니다.

위의 사항들만 고려하면 풀 수 있는 문제였습니다. 저도 Trie문제를 처음 풀어봐서 하루 넘게 끙끙 댄 문제입니다.

풀이 참조: ggodong.tistory.com/168

 

코드

class Node(object):
    
    def __init__(self, key, mark=0, data=None):
        self.key = key
        self.mark = mark
        self.data = data # leaf node는 전체 string, 나머지 node들은 None을 담고 있다.
        self.children = {}
        
class Trie(object):
    def __init__(self):
        self.head = Node(None)
    
    def insert(self, string):
        cur = self.head
        
        for char in string: # 각 캐릭터 순회
            # 해당 캐릭터가 트리에 없을경우 하위 노드로 추가
            if char not in cur.children: 
                cur.children[char] = Node(char)                
            cur = cur.children[char] # 현재 노드 변경

        # 마지막 노드의 경우 data를 스트링으로 변경하여 마지막 노드임을 명시
        cur.data = string    
    
    def marking(self, string):
        # insert 과정과 유사하나 삭제하지 말아야 하는 부분에 mark를 1로 설정한다.
        cur = self.head
        
        for char in string:
            cur.mark = 1
            if char not in cur.children:
                cur.children[char] = Node(char) 
            cur = cur.children[char]
        cur.mark = 1

    def remove(self, string):
        cur = self.head
        
        result = 0
        for char in string:
            # 해당 캐릭터가 있고 해당 캐릭터가 mark가 되어있으면 계속 순회
            if char in cur.children and cur.children[char].mark == 1:
                cur = cur.children[char]
            # 이미 삭제한 부분이면 종료해도 된다. 상위 명령어로 전부 삭제 가능하기 때문이다.
            elif cur.children[char].mark == 2:
                return result
            # 삭제가능한 경우 mark를 2로 바꿔주고 return 해준다.
            else:
                result += 1
                cur.children[char].mark = 2
                # print(cur.children[char].key)
                return result
        
        result += 1
        return result        

from sys import stdin
stdin = open("input.txt", "r")
# T: 테스트 케이스 개수
T = int(stdin.readline())
for t in range(T):

    trie = Trie()
    # N1: 지워야 하는 파일 개수
    N1 = int(stdin.readline())
    remove_list = []
    for _ in range(N1):
        remove_list.append(stdin.readline().strip())
        trie.insert(remove_list[-1])

    # N2: 지우지 말아야 하는 파일 개수
    N2 = int(stdin.readline())
    for _ in range(N2):
        trie.marking(stdin.readline().strip())

    # 지우는 과정
    answer = 0
    for i in range(N1):
        temp = trie.remove(remove_list[i])
        # print(remove_list[i], temp)
        answer += temp

    # 출력
    if N2 == 0: print(1)
    else: print(answer)