Algorithm/Baekjoon
[Python] Baekjoon 백준 1764번 듣보잡
Lute3r
2021. 9. 30. 00:35
[Python] Baekjoon 백준 1764번 듣보잡
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.
듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.
출력
듣보잡의 수와 그 명단을 사전순으로 출력한다.
import sys
num = {}
tmp = []
cnt = 0
n, m = map(int, input().split())
for _ in range(n+m):
s = sys.stdin.readline().strip()
if s not in num:
num[s] = 1
else:
num[s] += 1
for i in num:
if num[i] == 2:
cnt += 1
tmp.append(i)
print(cnt)
tmp.sort()
for i in tmp:
print(i)
리스트로 받아서 반복문을 통해 비교하는 형태로 하니까 시간초과 문제가 생겨서
딕셔너리 형태로 바꿔서 해보았다
for _ in range(n+m):
s = sys.stdin.readline().strip()
if s not in num:
num[s] = 1
else:
num[s] += 1
입력을 받을 반복 횟수를 n, m 상관 없이 합해서 입력받고
num 딕셔너리에 없으면 value 를 1 있으면 +1 하는 형태로 입력 받는다
for i in num:
if num[i] == 2:
cnt += 1
tmp.append(i)
딕셔너리의 키를 하나씩 빼서 해당 키의 값이 2 이면 즉, n 과 m 에서 한번씩 나와서 2가 된 요소 이면
cnt 카운트를 1씩 증가해주고, tmp 리스트에 append 해준다
print(cnt)
tmp.sort()
for i in tmp:
print(i)
출력 예제에 미리 2개 이상 인 갯수를 출력해야하기 때문에 cnt 를 이용해 먼저 출력해주고
sort 로 정렬을 해준다
그후 tmp에서 하나씩 빼서 출력해준다
반응형