Silver 2
x
- 시간 초과
문제 바로가기
가희는 블로그를 운영하고 있습니다. 가희는 블로그에 글을 쓰기 위해, 메모장에 키워드를 적곤 합니다.
지금까지 메모장에 써진 키워드는 모두 서로 다르며, 총 N개가 존재합니다.
가희는 새로운 글을 작성할 때, 최대 10개의 키워드에 대해서 글을 작성합니다.
이 키워드들 중에 메모장에 있었던 키워드는 가희가 글을 쓴 이후, 메모장에서 지워지게 됩니다.
가희는 블로그에 글을 쓰고 나서, 메모장에 있는 키워드 개수가 몇 개인지 알고 싶습니다. 가희를 도와주세요.
첫 번째 줄에 가희가 메모장에 적은 키워드 개수 N, 가희가 블로그에 쓴 글의 개수 M이 공백으로 구분해서 주어집니다.
2번째 줄부터 N+1번째 줄까지 메모장에 적은 키워드 N개가 주어집니다.
N+2번째 줄부터 N+M+1번째 줄까지, 가희가 쓴 글과 관련된 키워드가 , (쉼표)로 구분해서 주어집니다. 공백으로 구분되지 않음을 유의해 주세요.
x번째 줄에는 x번째 글을 쓰고 난 후에 메모장에 남아 있는 키워드의 개수를 출력해 주세요.
1 ≤ N ≤ 2×105
1 ≤ M ≤ 2×105
1 ≤ 글에 있는 키워드 개수 ≤ 10
1 ≤ 키워드 길이 ≤ 10
키워드는 소문자와 숫자로만 이루어져 있습니다.
메모장에 있는 키워드 이름은 중복되지 않습니다.
글에 있는 키워드 이름은 중복되지 않습니다. 그러나, 한 키워드는 여러 글에 있을 수 있습니다
5 2
map
set
dijkstra
floyd
os
map,dijkstra
map,floyd
3
2
완전 탐색이 가능한 범위는 아니라고 판단이 되었고 딕셔너리를 사용해 O(1)의 탐색 시간복잡도를 이용하려고 했다.
from sys import stdin
n,m=map(int,stdin.readline().split())
keywords=dict()
for _ in range(n):
keywords[stdin.readline().rstrip()]=True
for x in range(m):
write=list(stdin.readline().rstrip().split(','))
for y in write:
keywords[y]=False
answer=0
for x in keywords.values():
if x:
answer+=1
print(answer)
keywords의 요소를 하나씩 꺼내면서 True가 되어 있는지 확인하는 방법이었다.
keywords의 요소는 n개이고 m(n=m)번동안 반복 한다면 O(n2)의 시간이 발생하는 것이었는데 시간 초과가 날 수밖에 없었다.
keywords의 요소를 하나씩 꺼내면서 확인하는 것은 딕셔너리의 장점을 활용하지 못한 것이라고 할 수 있다.
from sys import stdin
n,m=map(int,stdin.readline().split())
keywords=dict()
answer=n
for _ in range(n):
keywords[stdin.readline().rstrip()]=True
for x in range(m):
write=list(stdin.readline().rstrip().split(','))
for y in write:
#모든 key()들 중 y 하나
if y in keywords.keys():
if keywords[y]:
keywords[y]=False
answer-=1
print(answer)
다음 방법은 최대 10의 길이인 write를 반복하고 그 요소가 keywords에 keys로 있다면 체크해주고 전체 길이에서 -1을 해주는 방법이다.
keywords는 딕셔너리이기 때문에 굳이 요소 하나 하나를 꺼내서 쓰지 않아도 y in keywords.keys()를 해주면 빠른 속도로 keys안에 y가 있는지 확인해준다.
다른 방법으로 keywords.get(y) 이런식으로 존재하는지에 대한 여부를 판단할 수 있다.
35:57
딕셔너리의 키나 밸류를 하나씩 꺼내서 비교하지 말고 in으로 비교하자.