[Baekjoon 22233] 가희와 키워드 | Python

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

---

문제

 

중복이 없는 메모장의 키워드에서 새로 작성되는 글에 사용된 키워드들을 제거했을 때 메모장에 남은 키워드의 개수를 구하는 문제이다.

 

---

풀이

 

가장 먼저 입력되는 값이 40만개까지 가능하므로, 빠른 입출력을 지원하는 sys 를 사용해야 한다.

메모장에 저장되는 키워드에는 중복이 없기에 새로 작성되는 글의 키워드를 메모장에서 삭제해주면 된다. 이때 새로 작성되는 글에 사용된 키워드가 메모장에 있는지 먼저 확인해야 하는데, 메모장 키워드들을 리스트로 저장한다면 리스트에서 키워드를 탐색할 때 순차적으로 탐색하기 때문에 시간이 오래 걸릴 수밖에 없다. 즉 in 을 활용해서 리스트에서 특정 값을 탐색할 경우 시간 복잡도는 O(N)이다.

따라서 리스트가 아니라 딕셔너리를 활용해서, 즉 해시 테이블을 사용해서 메모장에 글에 사용된 키워드가 있는지 확인해야 한다. 딕셔너리에서 in 을 활용해서 해당 값이 있는지 확인할 때 시간 복잡도는 O(1)이다.

키워드가 있는 것을 확인했다면 해당 키워드들 딕셔너리에서 제거해주면 된다.

마지막에는 해당 딕셔너리의 길이를 출력해주면 남은 키워드 개수를 확인할 수 있다.

 

---

코드

 

import sys

key_n, post_n = map(int, sys.stdin.readline().split())
memo = {}
for _ in range(key_n):
    memo[sys.stdin.readline().rstrip()] = True
for _ in range(post_n):
    post = list(sys.stdin.readline().rstrip().split(','))
    for post_item in post:
        if (post_item in memo):
            memo.pop(post_item)
    print(len(memo))