[algorithm] 백준 10815 - 숫자 카드 (파이썬)

📚 문제

입력

출력

예제 입력

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력

1 0 0 1 1 0 0 1

🧑🏻‍💻 풀이 과정

• 전형적인 이분탐색을 요구하는 문제.
• 비교할 카드를 0부터 비교할 카드의 길이 -1 동안 반복하며 상근이의 카드 중, 일치하는 카드가 나오면 1, 아니면 0을 ans에 저장하자.
• join을 이용해서 결과를 출력하자.
• 여담으로 딕셔너리나 set을 이용해서도 풀 수 있다고 한다.

import sys


def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if arr[mid] == target:
            return 1
        elif arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return 0


N = int(sys.stdin.readline().rstrip())
cards = sorted(list(map(int, sys.stdin.readline().rstrip().split())))
M = int(sys.stdin.readline().rstrip())
check_cards = list(map(int, sys.stdin.readline().rstrip().split()))

card_len = len(cards) - 1
ans = []
for card in check_cards:
    ans.append(binary_search(cards, card, 0, card_len))

print(" ".join(map(str, ans)))