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에서 하나씩 빼서 출력해준다

 

 

반응형