난이도

Silver 2

풀이 참고 유무

x

막힌 부분

1. 시간 초과

문제

문제 바로가기
가희는 블로그를 운영하고 있습니다. 가희는 블로그에 글을 쓰기 위해, 메모장에 키워드를 적곤 합니다.

지금까지 메모장에 써진 키워드는 모두 서로 다르며, 총 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)의 탐색 시간복잡도를 이용하려고 했다.

풀이(python)

Python - O(n2) 풀이(시간 초과)

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의 요소를 하나씩 꺼내면서 확인하는 것은 딕셔너리의 장점을 활용하지 못한 것이라고 할 수 있다.

Python - O(n) 수행시간

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으로 비교하자.