[백준/BOJ] 10815 - 숫자 카드

10815 - 숫자 카드

📌 문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

📋 코드

def binary_search(target, left, right):
    while left <= right:
        mid = (left + right) // 2

        if card[mid] == target:
            return 1
        elif card[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    return 0


N = int(input())
card = list(map(int, input().split()))
M = int(input())
check_card = list(map(int, input().split()))

card.sort()
result = []
for num in check_card:
    result.append(binary_search(num, 0, N-1))

print(*result)

💡 한마디

입력이 최대 *500,000 * 500,000 = 250,000,000,000* 개 들어올 수 있기 때문에 단순하게 이중 포문으로 풀면 시간초과 난다.

10815번: 숫자 카드