[python] 백준 1920번 시간초과 오답노트

이분탐색(Binary Search)으로 푸는 문제이다.
시간제한(1초)이 있는 이유가 이분탐색을 이용해서 풀라는 의도인 것 같다..

정답

n = int(input())
l_1 = set(map(int,input().split()))
m = int(input())
l_2 = list(map(int,input().split()))
for i in l_2:
    if i in l_1:
        print("1")
    else:
        print("0")

l_1을 list로하면 시간초과가 걸린다.
l_2는 for loop를 돌려야해서 iterable한 list로 해야한다.
l_1을 set로 변경하면 시간제한을 통과할 수 있다! 야호

이분탐색

그럼 이제 이분탐색에 대해 알아보자..

Binary Search 하는 법
1. 리스트를 정렬한다
2. 시작, 끝, 중간을 설정한다.
3. 중간 == i 면 탐색 끝!
4. 중간 <= i 면 시작 = 중간+1
5. 중간 >= i 면 끝 = 중간-1

그럼 이제 해볼까용~!

n = int(input())
l_1 = list(map(int,input().split()))
m = int(input())
l_2 = list(map(int,input().split()))
l_1.sort() #1번

for i in l_2:
    start, end = 0, n-1
    mid = 0 #2번
    exist = False

    while start <= end:
        mid = (start + end) // 2
        if l_1[mid] == i:
            exist = True
            print(1)
            break
        elif l_1[mid] > i:
            end = mid - 1
        else:
            start = mid + 1
    if not exist:
        print(0)