1. 문제 설명

수 찾기

2. 문제 분석

이분 탐색으로 해당 리스트 안에 특정 원소가 포함되어 있는지 확인한다. 이때 리스트는 정렬되어 있어야 한다.

• 이분 탐색의 기본 조건(start<end, mid 등)을 확인하는 문제
• heap을 통해 주어진 리스트를 정렬했는데, 파이썬 기본 모듈 sort를 사용해도 된다.

3. 나의 풀이

import heapq

n = int(input())
A = []
for num in map(int, input().split()):
    heapq.heappush(A, num)
sorted_A= []

while A:
    sorted_A.append(heapq.heappop(A))
# 리스트 정렬

m = int(input())
for num in map(int, input().split()):
    # num이 sorted_A에 존재하는지 이분 탐색으로 찾는다.
    start, end = 0, n-1

    is_in = False
    while start <= end:
        mid = (start + end) // 2
        if num == sorted_A[mid]:
            is_in = True
            break
        elif num < sorted_A[mid]:
            end = mid - 1
        else:
            start = mid + 1
    if is_in: print(1)
    else: print(0)