숫자 카드

백준 10815

시간초과나기 딱 좋은 문제 -> 이진탐색 이용해보기

이진탐색의 폼을 기억해두자!
이진탐색 함수를 선언하고, 이진탐색은 start, end, mid 세가지 변수를 사용한다. start<=end인 동안 while문을 반복한다. 또한 이진탐색은 정렬되어있을 때 사용할 수 있다는 것을 기억하자.

방법1. 이진탐색을 이용한다.

import sys

n = int(input())
have = list(map(int, sys.stdin.readline().split()))
m = int(input())
arr = list(map(int, sys.stdin.readline().split()))
# 이진탐색은 정렬되어 있는 상태에서 쓸 수 있다.
have = sorted(have)

def bisearch(n):
    start = 0
    end = len(have)-1
    while (start<=end):
        mid = (start+end)//2
        if have[mid] == n:
            return 1
        elif n > have[mid]:
            start = mid+1
        elif n < have[mid]:
            end = mid-1
    return 0

for ele in arr:
    print(bisearch(ele), end=" ")

have리스트는 상근이가 가지고 있는 숫자 카드이고,
arr리스트는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야하는 카드들이다.
그냥 생각했을 때 arr에 있는 원소들이 have리스트에 있는지를 확인하려면, have리스트 속 원소들을 돌면서 검사를 해야한다. 이걸 하나하나 검사하지 말고, 중간값을 설정해서 이 값보다 크면 큰 범위에서 찾고, 작으면 작은 범위에서 찾도록 이진탐색을 하자.
따라서 탐색해야할 have리스트를 정렬하고 have의 처음 인덱스, 마지막 인덱스를 start와 end로 설정해두고 이진탐색을 진행한다.