백준 1920 - 수 찾기

문제

https://www.acmicpc.net/problem/1920

 

 

풀이

# 백준 / 실버4 / 수 찾기

# 이진탐색 알고리즘
# 반드시 찾는 list가 정렬된 상태여야 한다.

def binary_search(target,list1):
    start = 0
    end = len(list1)-1
    
    while start <= end:
        mid = (start + end) // 2
        
        if list1[mid] == target:
            return 1
        
        elif list1[mid] > target:
            end = mid - 1
            
        else:
            start = mid + 1
    
    return 0

N = int(input())
list1 = list(map(int,input().split()))

M = int(input())
list2 = list(map(int,input().split()))

list1.sort()

for i in range(len(list2)):
    if binary_search(list2[i],list1) == 1:
        print(1)
    else:
        print(0)

 

그냥 풀었더니 시간초과

 

이제 슬슬 알고리즘을 적용해야 해결되는 문제들이 나온다

 

이진탐색으로 풀면 쉽게 해결 가능