BOJ 1746 듣보잡

https://www.acmicpc.net/problem/1746
시간 2초, 메모리 128MB
input :

• N, M(1 <= N, M <= 500,000)
• N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름

output :

• 듣보잡의 수와 그 명단을 사전순으로 출력

조건 :

• 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성

---

우선 나의 경우.
사람의 수는 최대한이 50만 명이다. 이를 배열에 저장하고, 다른 한 모임을 딕셔너리로 저장을 해서 모든 경우를 확인하게 한다면 이것도 시간복잡도가 100만 선에서 끝나지 않을까.

이렇게 할 수도 있고 아니면, 교집합을 이용하자. 어차피 우리는 겹치는 사람들을 찾아야 한다.
리스트 두개를 잠깐 set()으로 캐스팅 하여
&(합집합) 의 연산을 이용해 답을 구하자.

import sys

n, m = map(int, sys.stdin.readline().split())
data_1 = []
data_2 = dict()
for i in range(n):
    name = sys.stdin.readline().strip()
    data_1.append(name)

for i in range(m):
    name = sys.stdin.readline().strip()
    data_2[name] = 1

ans = []
for name in data_1:
    if data_2.get(name):
        ans.append(name)

ans.sort()
print(len(ans))
for name in ans:
    print(name)

https://dojinkimm.github.io/problem_solving/2019/09/26/boj-1764-deutbo.html
위의 분의 코드를 보고 가져왔다.

import sys

N, M = map(int, sys.stdin.readline().split())
data_1 = [sys.stdin.readline().strip() for i in range(N)]
data_2 = [sys.stdin.readline().strip() for i in range(M)]

ans = sorted(list(set(data_1) & set(data_2)).sort)

print(len(ans))
for name in ans:
    print(name)

역시 라이브러리를 이용해야 깔끔 해지는 구만.