[백준][Python] 1764 듣보잡

문제 링크

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

 

문제

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

 

입력

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

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

 

출력

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

---

풀이

# 이진 탐색
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

# 입력
n, m = map(int, input().split())
listen = [input() for _ in range(n)]
see = [input() for _ in range(m)]

# 사전순 탐색을 위한 정렬
listen.sort()
see.sort()

# 듣보잡 구하기
answer = []
for name in see:
    if binary_search(listen, name):
        answer.append(name)

answer.sort()

# 출력
print(len(answer))
for elem in answer:
    print(elem)

문자열을 사전순으로 나열 했을 때 순서에 따라 부등호 연산이 수행된다는 특성과 이진 탐색을 이용하여 listen(듣도)과 see(보도)에서 겹치는 항목을 구하였다. 사전순 출력을 위해 이진 탐색도 사전순으로 수행해야 하므로 미리 정렬을 해주었다. 그리고 빈 배열(answer)을 만들어 listen 배열과 see의 한 원소로 이진 탐색을 진행 하였을 때 동일한 항목이 나오면 answer(정답 배열)에 추가해 주었다.

# 입력
n, m = map(int, input().split())
listen = [input() for _ in range(n)]
see = [input() for _ in range(m)]

# set 활용
answer = list(set(listen) & set(see))
answer.sort()

# 출력
print(len(answer))
for elem in answer :
    print(elem)

set 자료형을 이용하여 중복을 삭제해 간단히 풀이가 가능하다... set을 잊지 말자...