BOJ 1920 - 수 찾기

문제

백준 온라인 저지 - 1920번

풀이 과정

주어진 배열에서 특정 수들이 존재하는지 판단하는 문제입니다.
배열의 길이와 찾는 수들이 각각 최대 10만이기 때문에 완전 탐색을 진행할 경우 시간 초과가 발생합니다.
따라서 검색용 배열을 미리 정렬한 뒤에 이분 탐색 을 이용해서 O(MlogN) 의 시간 복잡도로 해결할 수 있습니다.

코드

import sys


def find(arr, target):
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = (lo + hi) // 2

        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return False


def solution(number):
    return '1' if find(A, number) else '0'


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    M = int(input())
    questions = list(map(int, sys.stdin.readline().split()))

    A.sort()

    for question in questions:
        answer = solution(question)
        sys.stdout.write(f"{answer}\n")