Python3/백준 알고리즘
2022.02.26 [백준] (python 파이썬) 듣보잡
ian's coding
2022. 2. 26. 00:42
728x90
반응형
https://www.acmicpc.net/problem/1764
1764번: 듣보잡
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다.
www.acmicpc.net
풀이
이 문제는 arr1, arr2에 모두 속하는 데이터를 뽑은 뒤 갯수를 출력하고, 사전순으로 데이터를 출력하면 된다.
처음 쉽게 생각하고 두개의 배열을 모두 리스트로 만들어 코드를 작성했지만 시간초과가 발생했다.....
그래서 시간 복잡도를 생각하던 중 set은 포함유무를 체크하는데 O(1)이라는 시간이 걸린다는 것이 생각났다!!
참고로 list는 포함유무를 체크하는데 O(N)이다...
그래서 두 배열을 set으로 만들고 for문을 돌려 arr1의 데이터가 arr2에 있으면 정답 배열에 담고 정렬한 후 출력했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
import sys
input=sys.stdin.readline
n,m=map(int, input().split())
arr1=set()
arr2=set()
ans=[]
for _ in range(n):
arr1.add(input().rstrip())
for _ in range(m):
arr2.add(input().rstrip())
for i in arr1:
if i in arr2:
ans.append(i)
ans.sort()
print(len(ans))
for i in ans:
print(i)
|
cs |
728x90
반응형