[백준][이분 탐색] - 10815. 숫자 카드

오답 - 시간 초과

n = int(input())
card = list(map(int,input().split()))

m = int(input())
a = list(map(int,input().split()))
res = []
for i in a:
    if i in card:
        res.append(1)
    else:
        res.append(0)
for i in res:
    print(i, end=" ")

문제 풀이 - 이분 탐색 X 

n = int(input())
card = set(map(int,input().split()))

m = int(input())
a = list(map(int,input().split()))

for i in a:
    if i in card:
        print(1,end = " ")
    else:
        print(0, end = " ")

• set을 사용해서 다시 풀었더니 맞춘 문제이다. 
• 혹시나 해서 다시 list를 append하지 않고 위와 같이 바로 출력해주는 방식으로 진행했으나 똑같이 시간초과가 나온다.

문제 풀이 - 이분 탐색 O

def binary_search(m):
    start = 0
    end = n-1
    while start <= end:
        mid = (start + end) // 2
        if card[mid] == m:
            return 1
        elif card[mid] > m:
            end = mid - 1
        else:
            start = mid + 1

    return 0

n = int(input())
card = list(map(int,input().split()))
card.sort()

m = int(input())
a = list(map(int,input().split()))

for i in a:
    print(binary_search(i), end=" ")

• 이 경우엔 해당 값이 무조건 맞아야 1로 나타날 수 있기 때문에 3가지 경우로 나누어 진행하였다.
  • 다른 포스팅을 보면 알 수 있겠지만 다른 경우는 많더라도 포함하는 경우가 있어서 2가지 경우를 살펴보았다!