[알고리즘/문자열] 22233번 가희와 키워드: - python

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

22233번: 가희와 키워드

 

---

• 문제
• 소요시간: 14분 45초

 

---

• 설계하기(접근방법) 

1. 입력받기

입력받을 문자가 많으니 sys를 통해 입력받는다

 

2. 구현하기

입력과, 테스트의 수가 4억개까지 늘어날 수 있으니 시간초과에 주의해야 하는 문제다

 

단어의 중복을 허용하지 않으니

딕셔너리로 구현하여 탐색한다면

시간을 많이 줄일 수 있다

 

먼저 입력받은 메모장을 모두 딕셔너리에 넣어준 후

dict[key] = 1이라고 선언해준다

 

그 후 글로 쓴 키워드 내에 단어가 dict에 있다면

dict에서 삭제해준 후, 전체 dict의 길이에서 -1을 해준다

 

### 처음에는 없어진 단어를

dict[key] = 0으로 해준 후

dict[key] = 1인 단어의 개수를 세서

아직 남아있는 단어의 수를 세려고 했다

하지만 시간초과를 받고 필요없는 연산을 제거하기로 했다

 

없어진 단어는 단어장에서 삭제해도 되고 -> 추후에 단어장을 탐색할 때 시간을 줄일 수 있음

단어를 삭제할 때마다 남은 단어의 개수를 세지 않고

전체 개수를 선언한 후 단어를 삭제할 때마다

cnt를 1씩 감소시켜주면 된다

 

 

3. 출력하기

테스트 케이스 때마다 cnt를 출력해준다

 

 

---

• 코드(출력)

import sys

input= sys.stdin.readline

key_word, write = map(int,input().split())
key_dict = {}

for i in range(key_word):
    key = input().rstrip()
    key_dict[key] = 1

cnt = len(key_dict)
for i in range(write):
    write_list = input().rstrip().split(',')
    for j in write_list:
        if j in key_dict:
            del key_dict[j]
            cnt -= 1
    print(cnt)

---

• 얻어갈 부분

1. 시간이 촉박하게 선언된 문제들은, 시간을 어떻게 줄일 수 있을지 논리적으로 생각해보자

2. split을 활용하여 문자를 쉽게 입력받을 수 있게 응용했다