[BOJ, Python] 1763번 : 듣보잡

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

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

예제 입력 1

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1

2
baesangwook
ohhenrie

 

풀이

처음에 풀었을때 시간초과로 계속 틀렸습니다. 빠른 입출력으로 돌려봐도 시간초과가 뜨는걸 보아 코드에 문제가 있었어요. 이 문제에서 N, M이 500,000 이하의 자연수라서 리스트 자료형을 쓰면 시간초과가 뜨는 것이었습니다.

 

다음은 시간초과가 뜬 코드입니다.

N, M = map(int, input().split())
# 듣도 못한 사람 : N, 보도 못한 사람 : M
# N + 2째 줄 부터 보도 못한 사람
deutbo_list = []
deut_list = []

for i in range(N + M):
    name = input()

    if i < N:
        deut_list.append(name)
    else:
        if name in deut_list:
            deutbo_list.append(name)

deutbo_list.sort()

print(len(deutbo_list))

for deutbo in deutbo_list:
    print(deutbo)

듣도 못한 사람을 N번 list에 입력받고, N + 1번 ~ M번 까지 입력을 받은 뒤 받을 때마다 deut_list에 똑같은게 있는지 판별했습니다. 이러니 시간초과가 뜰수밖에 없었네요..

 

다음은 집합 자료형을 사용해 풀이한 코드입니다.

N, M = map(int, input().split())
# 듣도 못한 사람 : N, 보도 못한 사람 : M
# N + 2째 줄 부터 보도 못한 사람
deut_set = set()
bo_set = set()
deutbo_set = set()

for i in range(N + M):
    name = input()

    if i < N:
        deut_set.add(name)
    else:
        bo_set.add(name)

deutbo_list = list(deut_set.intersection(bo_set))
deutbo_list.sort()

print(len(deutbo_list))

for deutbo in deutbo_list:
    print(deutbo)

듣도 못한 사람을 저장하는 집합, 보도 못한 사람을 저장하는 집합을 따로 만들었습니다. 그리고 deut_set과 bo_set을 교집합 연산을 통해 같은 원소만 추출합니다. 정렬을 위해 list 자료형으로 바꿔서 deutbo_list에 저장하고 원하는 출력을 위한 코드를 작성해 줍니다.

 

어떻게 보면 단순한 문제이지만 공통되는 원소를 찾을때는 집합 자료형을 쓰는게 시간복잡도가 낮다는 것을 알게되었습니다 :)