백준 10815 파이썬 숫자 카드

 

 

처음에는 그냥 하나하나 다 탐색해야 하는 건 줄 알고 가볍게 풀었다.

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split()))

for i in range(len(B)):
    if B[i] in A:
        B[i] = 1
    else:
        B[i] = 0

for i in B:
    print(i, end=' ')

쉽다쉬워~ 

그런데 계속 시간초과가 뜬다.

알고리즘 뭐 쓰이는지 봤더니 이분탐색..!

주어지는 리스트의 크기가 작지 않은 이상 전체 탐색은 시간이 너무 오래 걸리는 것이었다

 

 

 

 

 

 

import sys

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split()))
A.sort()


def binary_search(num):
    l = 0
    r = N - 1
    while l <= r:
        mid = (l + r) // 2
        if A[mid] == num:
            return 1
        elif A[mid] > num:
            r = mid - 1
        else:
            l = mid + 1
    return 0


for i in B:
    print(binary_search(i), end=' ')

 

왼쪽을 l, 오른쪽을 r 이라고 지정하고 가운데를 mid = (l + r) // 2로 정의

찾는 수는 num

찾는 수와 같으면 1을 리턴하고,

찾는 수가 mid 보다 더 작으면 왼쪽 반에서 다시 찾고 (r = mid - 1 로 다시 지정)

찾는 수가 mid 보다 더 크면 오른쪽 반에서 다시 찾는다 (l = mid + 1 로 다시 지정)

그리고 없다면 0을 리턴하면 된다