[Baekjoon 1920 / python / 실버4] 수 찾기

import sys

# 이분 탐색 알고리즘 함수

def binarySearch(originList, n, data): # 배열, 배열 길이, 찾을 값

    start = 0

    end = n - 1

    while start <= end:

        mid = (start + end) // 2

        if originList[mid] == data:

            return True

        elif originList[mid] < data:

            start = mid + 1

        else:

            end = mid - 1

    return False

n = int(sys.stdin.readline())

originList = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())

goodList = list(map(int, sys.stdin.readline().split()))

originList.sort() # 이분 탐색을 위한 정렬

originLen = len(originList) # 이분 탐색을 위한 배열 길이 구해놓기

for i in goodList:

    if binarySearch(originList, originLen, i):

        print('1')

    else:

        print('0')

 

정말 간단해 보이지만 시간 초과 때문에 쉽게 틀리곤 하는 문제다.

이 문제는 이분 탐색 알고리즘만 알면 아주 간단하게 풀 수 있다.

 

binarySearch() 함수가 이분 탐색 알고리즘을 구현한 함수이다. originList에 값이 있는지 확인할 때, binarySearch()를 사용해 주기만 하면 끝이다.