[코딩테스트 공부] 듣보잡

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

우선 문제부터 분석을 해봅시다

일단 N, M의 조건과 시간 제한 조건을 확인해봅시다.

N, M의 경우 각각 500000까지 허용이 되고, 시간 제한은 2초인 상황입니다. 그리고 두 리스트를 입력받아서 탐색을 해야하는 상황인데요, 탐색의 경우에는 O(N^2), O(NlogN)의 복잡도를 채택할 수 있습니다. 혹은 투포인터 기법을 사용할 수도 있겠으나, 문제가 범위를 좁혀나가는 것에 초점이 있는 상황이 아니기 때문에, O(NlogN)의 복잡도를 가지는 이진탐색 으로 구현할 예정입니다.

코드부터 확인해볼까요

import sys

input = sys.stdin.readline

def binary_search(search_data, target_list, start, end):
    if start > end:
        return None

    mid = (start + end) // 2
    
    if target_list[mid] == search_data:
        return mid
    elif target_list[mid] > search_data:
        end = mid - 1
    else:
        start = mid + 1
        
    return binary_search(search_data, target_list, start, end)

N, M = map(int, input().split())

no_listen_list, no_looked_list = [], []
result_list = []

for _ in range(N):
    no_listen_list.append(input().strip())
    
for _ in range(M):
    no_looked_list.append(input().strip())
    
no_listen_list = sorted(no_listen_list)
no_looked_list = sorted(no_looked_list)

for person in no_looked_list:
    if binary_search(person, no_listen_list, 0, N - 1) != None:
        result_list.append(person)

print(len(result_list))

for person in result_list:
    print(person)

우선은 출력 순서가 오름차순 출력이기 때문에, 탐색 대상의 리스트만 정렬을 하는 것이 아니라 순회할 리스트도 동시에 정렬을 해줍니다.

그리고 이진 탐색을 이용해서 탐색을 함으로써 result_list에는 정답에 해당하는 사람의 이름만이 담기게 됩니다.

간단하죠?