백준 알고리즘 파이썬(Python) 10815번 숫자카드

---

주어지는 값이 매우 크기 때문에 if - in 구문을 쓰는 순차 탐색을 이용하면 시간 초과가 난다

따라서 탐색시간을 획기적으로 줄여주는 이분 탐색을 이용해야 한다.

이분 탐색을 활용할 줄 안다면 간단한 문제이다.

 

아래는 원하는 원소의 위치를 알려주는 이분 탐색의 기본적인 코드이다.

(재귀를 사용하는 방법도 있지만 이 코드가 제일 간단하고 이해하기 쉬운 것 같다.)

 

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

 

따라서 이 이분 탐색 함수를 이용해 문제를 풀어주면 아래의 답이 나온다.

 

import sys

n = int(input())
card = list(map(int, sys.stdin.readline().split()))
m = int(input())
check = list(map(int, sys.stdin.readline().split()))

card.sort() #이분탐색을 해주려면 우선 정렬 해주어야 한다.

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

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None


for i in range(m):
    if binary_search(card, check[i], 0, n - 1) is not None: #원하는 숫자가 있다면 1 출력
        print(1, end=' ')
    else:
        print(0, end=' ')