2021.2.5 [백준] 듣보잡

이진 탐색 알고리즘

 

 

Q

 

www.acmicpc.net/problem/1764

1764번: 듣보잡

 

A

 

이진 탐색 알고리즘을 이용해 풀었다. 주의할 점은 듣보잡의 명단 제출시 사전순으로 출력해야 한다는 점이다.

 

코드

n, m = map(int, input().split()) 
array = list(input() for _ in range(n))
target_list = list(input() for _ in range(m))

 

array.sort() #이진 탐색을 위한 오름차순 정렬

 

def binary(array, target, start, end): #이진 탐색 실행
    while start <= end:      
        mid = (start + end) // 2
        if array[mid] == target:
            return 1 #이 문제는 명단에 있는지가 중요하고 위치는 중요하지 않기에 1을 리턴
        elif array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None
    
result = []
count = 0
for k in range(m):
    if binary(array, target_list[k], 0, n - 1) == 1: 

        result.append(target_list[k])

        count += 1

 

print(count) #듣보잡의 수 먼저 출력

result.sort() #사전순 출력을 위해 오름차순 정렬

print('\n'.join(result)) #리스트를 문자열로 변환한 다음, \n을 이용하여 줄바꿈하여 출력하였다.