[Python] 2776번 암기왕

✏️ 문제

문제 파악

이 문제는 이분 탐색을 써서 풀 때 함수를 안쓰면 시간 초과가 뜬다 .. (나만 그런가)

 

그리고 출력이 수첩2에 있는 숫자를 기준으로 1, 0 출력이 되므로 수첩2는 정렬하면 안된다. 

수첩1을 정렬하고 수첩1의 요소를 가지고 이분 탐색을 하면 쉽게 풀 수있다.

 

알고리즘

• 자료 구조
• 정렬
• 이분 탐색
• 해시를 사용한 집합과 맵

 

 

코드

import sys
input = sys.stdin.readline

def bs(start, end, note1, i):
    while start <= end: 
      mid = (start + end) // 2
      
      if note1[mid] == note2[i]: 
        return 1 
      elif note1[mid] > note2[i]:
        end = mid - 1
      else:
        start = mid + 1
    return 0 

for _ in range(int(input())):
    n = int(input())
    note1 = sorted(list(map(int,input().split())))
    m = int(input())
    note2 = list(map(int,input().split())) 

    for i in range(m):
      print(bs(0, n-1, note1, i))