10815. 숫자 카드

문제

백준 10815번 숫자 카드

---

풀이

굉장히 오랜만에 쓰는 포스팅이다.. 개강하고 너무 정신없이 바빠,,,

이분탐색의 대표적인 문제다.

정렬된 리스트에서 어떠한 숫자 x가 존재하는지 탐색하기 위해 중앙값을 두고 비교한다.

중앙값이 찾으려는 값 x보다 크면
-> 중앙값을 포함해 중앙값 이후의 숫자들은 배제한다.

중앙값이 찾으려는 값 x보다 작으면
-> 중앙값을 포함해 중앙값 이전의 숫자들은 배제한다.

import sys

n = int(sys.stdin.readline())
sg = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

sg.sort()
for num in nums:
    l, r = 0, len(sg)-1
    while l <= r:
        mid = (l+r)//2
        if sg[mid] == num: 
            print(1, end=' ')
            break
        elif sg[mid] > num:
            r = mid-1
        else:
            l = mid+1
    else: print(0, end=' ')