문제

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

풀이

수의 크기 만큼 배열을 선언하고 찾는 방법도 있겠지만 더 제한을 두고,
이분 탐색을 사용하여 풀었다.

코드

import sys
input = sys.stdin.readline

a = int(input())
N = list(map(int, input().split()))
b = int(input())
M = list(map(int, input().split()))

N.sort()

def bs(x):
    l = 0
    r = a - 1
    while l <= r:
        m = (l + r) // 2
        if N[m] == x:
            return 1
        elif N[m] > x:
            r = m - 1
        elif N[m] < x:
            l = m + 1
    return 0


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

다른 풀이 코드

import sys
input = sys.stdin.readline

a = int(input())
N = list(map(int, input().split()))
b = int(input())
M = list(map(int, input().split()))

dict = {}

for i in range(a):
    dict[N[i]] = -1

for i in M:
    if i in dict:
        print(1, end=' ')
    else:
        print(0, end=' ')


print(dict)

dictionary 자료형으로 key: value 형태로 내부적으로 해시 테이블을 기반으로 하기 때문에 빠르게 값을 찾을 수 있다.

이를 이용하여 풀 수도 있다.