[백준] 1920 파이썬(python) : 수 찾기 - (이분탐색)

1920번: 수 찾기

 

 

 

 

이분탐색을 사용하지 않은 풀이)

n = int(input())
arr = set(map(int, input().split())) #1
m = int(input())
search_num = list(map(int, input().split()))
for num in search_num:
    print(1) if num in arr else print(0)

 

 

#1 : 파이썬의 in 함수 사용시 찾아야할 값을 줄여주기 위해 set으로 중복값을 지워준다.

 

 

set으로 중복값을 지워주지 않으면 '시간 초과'가 발생한다.

 

 

이분탐색을 사용한 풀이)

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
search_number = list(map(int, input().split()))
arr.sort()

for num in search_number:
    check = False
    start, end = 0, n-1
    while start <= end:
        mid = (start+end) // 2
        if num == arr[mid]:
            check = True
            print(1)
            break
        elif num < arr[mid]:
            end = mid - 1
        else:
            start = mid + 1
    if check == False:
        print(0)

 

 

나의 풀이)

import sys
n = int(sys.stdin.readline())
number = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
find_number = list(map(int, sys.stdin.readline().split()))
number.sort()

start, end = 0, n-1
def binary_search(start, end, target):
    global check
    check = False
    while start <= end:
        mid = (start+end) // 2
        if number[mid] == target:
            check = True
            return
        elif number[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return

for i in find_number:
    check = False
    binary_search(0, n-1, i)
    if check == True:
        print(1)
    else:
        print(0)

 

 

파이썬을 이용하면 이분탐색을 사용하지 않아도 풀 수 있지만 예제에는 없는 테스트 케이스를 생각해볼 수 있는 문제였다.