2021.2.4 [백준] 수 찾기

이진 탐색 알고리즘

 

 

Q

 

www.acmicpc.net/problem/1920

1920번: 수 찾기

 

A

 

이진 탐색 알고리즘과 이중반복문 두가지 방법으로 풀었다. 다만, 이중반복문의 경우 시간초과 가능성이 높다.

 

1) 이진 탐색 알고리즘 코드

n = int(input())
array = list(map(int, input().split()))
m = int(input())
target_list = list(map(int, input().split()))

 

array.sort() #이진 탐색을 위해서는 반드시 정렬해야한다!!

 

def binary(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return None

for k in target_list: #찾아야 하는 타겟이 리스트 형태로 있으므로 반복문 생성
    if binary(array, k, 0, n - 1) != None: #시작점은 언제나 0으로, 끝점은 언제나 n - 1로 하는게 좋다.
        print(1)
    else:
        print(0)

 

2) 이중 반복문 코드

n = int(input())
array = list(map(int, input().split()))
m = int(input())
target_list = list(map(int, input().split()))

for i in target_list:
    if i in array:
        print(1)
    else:
        print(0)