BOJ 1746 듣보잡
7736 단어 2021.02.192021.02.19
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)
역시 라이브러리를 이용해야 깔끔 해지는 구만.
Author And Source
이 문제에 관하여(BOJ 1746 듣보잡), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-1746-듣보잡저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)