듣보잡
solved_ac[Class3][듣보잡](https://www.acmicpc.net/problem/1764)
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
예제 입력 1
3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton예제 출력 1
2
baesangwook
ohhenrie문제 해석
리스트와 튜플의 시간 복잡도는 O(n)이지만 set과 dictionary의 시간 복잡도는 O(1)이다. 리스트를 이용해서 교집합을 찾아내는 것보다 set이나 dict을 이용해서 교집합을 찾는것이 훨씬 빠르다.
첫번째 풀이(dict 사용)
- 딕셔너리 변수를 선언해준다.
- 딕셔너리에 입력받은 문자열들을 key 값으로 넣어주고 value 값은 1로 만든다. 어차피 value는 사용하지 않는다. dict을 쓴 이유는 key와 value 때문이 아닌 시간복잡도가 O(1)인 in 연산자를 사용하기 위함이다.
- M만큼 루프를 돌면서 입력받은 문자열 a가 딕셔너리 안에 존재를 한다면 res 리스트에 넣어준다. 여기서 왜 res는 리스트를 쓰냐? 사전 순으로 출력하기 위해서 sort 함수를 쓸 것이기 때문이다.
- sort를 해서 사전 순으로 나열한다.
주의
dict의 in 연사자를 이용한 return 값은 해당 key에 해당하는 value 값이 아닌 True 혹은 False가 나온다.
예를 들어 "a" in dict 를 하였을 때, dict 안에 key 값으로 a라는 문자가 있다면 결과는 True가 나오게 되고, 없다면 False가 나온다.
dict 코드
import sys
N, M = map(int, sys.stdin.readline().split())
str_list1 = dict()
res = []
for i in range(N):
a = sys.stdin.readline().rstrip()
if a not in str_list1:
str_list1[a] = 1
for i in range(M):
a = sys.stdin.readline().rstrip()
if a in str_list1:
res.append(a)
res.sort(reverse = False)
print(len(res))
for i in res:
print(i)두번째 풀이(set 사용)
- 두 개의 set을 선언해준다.
- 각자 입력받은 문자열들을 add를 통해 넣어준다. list()는 문자열을 넣어주려면 append()를 이용해서 넣는데 set()은 add()를 이용하여 넣는다.
- set에서의 연산자 &를 이용하여 교집합을 뽑아내고 list화 시킨다.
- 결과 리스트를 sort 함수를 이용하여 사전 순으로 나열한다.
set 코드
import sys
N, M = map(int, sys.stdin.readline().split())
str_lst1 = set()
str_lst2 = set()
for i in range(N):
str_lst1.add(sys.stdin.readline().rstrip())
for i in range(M):
str_lst2.add(sys.stdin.readline().rstrip())
res = list(str_lst1 & str_lst2)
res.sort(reverse = False)
print(len(res))
for i in res:
print(i)결론
set의 & 연산자와 dict의 in 연산자는 시간복잡도가 평균 O(1)이다. 하지만 list()와 tuple()은 시간복잡도가 O(n)이다. 즉 이 문제에서 list와 tuple을 사용하면 시간초과가 뜨게 된다. 중복이 있거나 해당 문자나 숫자 등을 찾아내는 문제인 경우 dict나 set을 적절히 조합해서 사용하도록 하자.
