[백준] 10815번 숫자 카드 - 파이썬

https://www.acmicpc.net/problem/10815

10815번: 숫자 카드

풀이:

단순 비교로 생각한다면 제한시간인 2초를 넘어버린다. 단순 계산으로 생각해 보면, 최대 개수인 500,000개를 500,000번 비교해야 되니 for문을 총 250,000,000번 반복해야 한다. 100,000,000번 연산이 통상 1초 정도 걸린다고 알려져 있기 때문에 단순 비교는 약 2.5초 정도 걸릴 것이다. 따라서 숫자 카드를 담고 있는 배열을 정렬해 준 뒤 이분 탐색으로 찾고자 하는 값이 들어있는지 안 들어있는지 확인하면 된다. 이분 탐색 알고리즘은 logN의 시간복잡도를 가지고 logN은 반절만 계산하기 때문에 쉽게 생각해서 시간이 반 정도밖에 안 걸린다고 생각하면 된다.

 

코드:

n = int(input())
N = list(map(int, input().split()))
m = int(input())
M = list(map(int, input().split()))
N.sort()


def bs(x):
    low = 0
    high = n - 1

    while low <= high:
        mid = (low + high) // 2
        if N[mid] == x:
            return 1
        elif x < N[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return 0


for i in M:
    print(bs(i), end=' ')