[Baekjoon]백준 2776 암기왕(실버 4) - Python

문제설명

문제를 살펴보면 수첩1에 정보들을 입력받고, 수첩2에 또 다시 정보를 입력받아 수첩2에 적힌 정보가 수첩1에 존재한다면 

1을, 아니라면 0을 출력하는 간단한 문제이다 허나, 숫자를 탐색하는 방법은 다양하지만 리스트로 입력받고 리스트로

값을 찾게 된다면 시간 출력이 발생한다

따라서 이분탐색 또는 집합 등 다른 방법을 통해 숫자의 존재 여부를 확인해야한다

 

알고리즘 연습을 위해 문제를 풀고있기때문에 해당 문제를 이진탐색 함수를 직접 구현하여 해결하였다

함수에 low, high, find(찾고자하는 값)을 전달한 후, low가 high보다 커질때까지 mid의 값을 조절하면서 값을 찾아나가면 된다

mid는 low와 high의 중간값으로 설정하고, 만약 해당 위치의 값이 찾고자하는 값보다 크다면 high의 값을 조절하고

그 반대라면 low의 값을 조절하면 된다(수첩1의 정보는 sort()를 통해 정렬되어있어야함)

mid에 위치한 값이 찾고자 하는 수와 동일하다면 1을 반환하고, 만약 while문을 빠져나오게 된다면(원하는 수를 찾지 못했다면)

0을 반환하면 문제의 조건을 성립하게된다

import sys
input = sys.stdin.readline

def binary_search(low, high, find):
    while low <= high:
        mid = (low + high) // 2
        if note1_info[mid] == find:
            return 1
        elif note1_info[mid] < find:
            low = mid + 1
        else:
            high = mid - 1
    return 0

test_case = int(input())
for _ in range(test_case):
    note1_num = int(input())
    note1_info = list(map(int, input().split()))
    note1_info.sort()
    
    note2_num = int(input())
    note2_info = list(map(int, input().split()))
    
    for f in note2_info:
        print(binary_search(0, note1_num - 1, f))