[알고리즘/백준] 10815번 숫자 카드 Python 파이썬

이 문제는 이분 탐색을 이용하여 푸는 문제이다. 

 

 

위와 같은 조건을 가지며 여기서 시간 복잡도를 생각해 일일이 비교하여 찾는 것이 아닌(이 방법으로 풀면 시과 초과가 나서 통과가 안된다.) 단축을 위한 알고리즘으로 이분 탐색을 이용한 것이다. 이분 탐색에 대해 자세히 알고 싶다면 아래 링크를 참고하면 좋다. 움직이는 그림을 통해서 이해하기 쉽게 알 수 있다.

 

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)

 

다음과 같은 코드를 통해 통과하였다.

 

import sys
input = sys.stdin.readline

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

N_list.sort()

def binary_search(N_list, M_num, start, end):
    while start <= end:
        mid = (start+end) // 2
        if N_list[mid] == M_num:
            return 1
        elif N_list[mid] > M_num:
            end = mid - 1
        else:
            start = mid + 1
    return 0

for i in range(M):
    print(binary_search(N_list, M_list[i], 0, N-1), end=' ')

 

이분 탐색을 이용하면 시간 복잡도는 아래와 같으면 최종적으로 log N 이다.