[백준 알고리즘] 1764번: 듣보잡 (파이썬 / Python)

문제

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

입력

 

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

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

출력

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

예제 입력

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력

2
baesangwook
ohhenrie

---

문제 접근

들어보지 못한 사람, 보지 못한 사람의 명단이 각각 주어지는데, 두 명단에 모두 속해있는 사람의 수와 그 이름을 사전순으로 출력하면 된다.

정답 코드

#1764번: 듣보잡

import sys
n, m = map(int, sys.stdin.readline().split())
n_set = set()
m_set = set()
nm_list = []

for i in range(n+m):
    check = sys.stdin.readline().rstrip()
    if i < n:
        n_set.add(check)
    else:
        m_set.add(check)
    nm_list.append(check)

count = 0
print_list = []
for i in sorted(set(nm_list)):
    if i in n_set and i in m_set:
        count += 1
        print_list.append(i)

print(count)
print("\n".join(print_list))

나의 답안이다.

n_set(들어보지 못한 사람 명단)

m_set(보지 못한 사람 명단)

두 집합을 각각 생성한다. 여기서 list가 아닌 set으로 구현한 이유는, 명단에 있는지 없는지 검사하기 위한 목적이므로 set이 적합하며 시간초과를 예방하기 위함이다.

for i in range(n+m):
    check = sys.stdin.readline().rstrip()
    if i < n:
        n_set.add(check)
    else:
        m_set.add(check)
    nm_list.append(check)

명단을 입력받는 부분이다. n+m만큼 입력받고, n보다 작을 때(즉, 들어보지 못한 사람의 명단)까지는 n_set에 추가하고,

그 이후는 m_set에 추가한다.

별도로 nm_list를 만들어 모든 이름을 다 추가한다.

count = 0
print_list = []
for i in sorted(set(nm_list)):
    if i in n_set and i in m_set:
        count += 1
        print_list.append(i)

print(count)
print("\n".join(print_list))

다음 부분이다. 출력을 위한 count 변수를 선언, for문으로 sorted(set(nm_list))를 순회하며,

n_set과 m_set에 모두 속하는지 검사하고, 있다면 카운트하고 print_list에 추가한다.

(정렬을 시키는 이유는 사전순 출력을 위함이고, 집합으로 만든 이유는 중복 출력을 방지하기 위함이다.)

카운트를 출력하고, print_list를 join함수를 이용해 출력했다.

 

 

---

1764번: 듣보잡