728x90
https://www.acmicpc.net/problem/10815
각 배열을 처음부터 끝까지 탐색하면 시간초과가 나도록 유도하는 문제이다.
O(log n)의 시간복잡도를 가지는 이분탐색을 활용해야한다.
상근이가 가지고 있는 숫자카드가 비교할 배열보다 작으니까, 숫자카드에서 수를 하나 뽑아서 상근이의 숫자카드 목록에 있는지 찾아주면 된다.
import sys
def binary_search(arr, num,left,right):
while left <= right:
mid = int((left + right) /2)
if arr[mid]==num:
return True
elif arr[mid] < num:
left = mid +1
else :
right = mid -1
return False
n = int(input())
card =list(map(int, sys.stdin.readline().split()))
m = int(input())
cmp = list(map(int, sys.stdin.readline().split()))
card = sorted(card)
for i in cmp:
if binary_search(card, i,0,n-):
print(1, end= ' ')
else:
print(0, end=' ')
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 1929번 소수 구하기 (0) | 2022.10.24 |
---|---|
[백준/파이썬] 11650번 좌표 정렬하기 (0) | 2022.10.21 |
[백준/파이썬] 1789번 수들의 합 (0) | 2022.10.07 |
[백준/Python] 2163번 초콜릿 자르기 (0) | 2022.10.06 |
[백준/Python] 2588번 곱셈 (0) | 2022.10.03 |