📢 10815번 문제

백준 문제 링크

🔎 풀이

사용 언어 :python
단순 if문과 in을 활용하면 시간초과
이진탐색을 활용하여 풀기
start : 탐색 범위 시작 인덱스
end : 탐색 범위 마지막 인덱스
mid : 탐색 범위 중간값

💡이분 탐색/이진 탐색

이분 탐색(Binary Search)이란?
정렬되어 있는 배열에서 데이터를 찾으려 할때 전체 데이터에서 찾는 것이 아니라
탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.

동작방식
1. 배열의 중간값 결정
2. 중간값과 검색값을 비교
3. 중간값 == 검색값 이면 종료, 중간값 > 검색값이면 왼쪽 구간 탐색, 중간값 < 검색값 이면 오른쪽 구간 탐색
4. 반복

🔎코드

• 시간초과

N = int(input())

N_card = list(map(int, input().split()))

M = int(input())

num = list(map(int, input().split()))


def Card(y):
    if y in N_card:
        return 1
    else:
        return 0


result = list(map(Card, num))

print(*result, end=" ")

• 이진 탐색 이용

N = int(input())

N_card = list(map(int, input().split()))
N_card.sort()

M = int(input())

num = list(map(int, input().split()))


def BinarySearch(y):
    start = 0
    end = N-1
    while start <= end:
        mid = (start + end)//2
        if N_card[mid] == y:
            return 1
        elif N_card[mid] > y:
            end = mid-1
        else:
            start = mid + 1
    return 0


result = list(map(BinarySearch, num))
print(*result, end=" ")