[백준 문제풀이] 10815 - 숫자 카드

백준 문제풀이 10815번

풀이

간단한 탐색문제이고, 선형탐색으로 문제를 풀이할 시 $O(N^2)$로 시간초과가 발생할 확률이 높다. 그래서 이분탐색으로 문제를 풀이하면 정답처리가 된다. 문제를 풀고 확인해보니 파이썬에서는 집합이나 딕셔너리를 이용해 in함수로 문제를 간단하게 풀어버리는 방법도 존재했다.

코드

import sys
 
print = sys.stdout.write
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

M = int(input())
table = list(map(int, input().split()))

for i in range(len(table)):
    answer = 0
    start = 0
    end = len(arr) - 1

    while start <= end:
        middle = (start + end) // 2

        if table[i] == arr[middle]:
            answer = 1
            break
        elif table[i] > arr[middle]:
            start = middle + 1
        elif table[i] < arr[middle]:
            end = middle - 1

    print("".join(str(answer) + " "))