'수첩2'에 적혀있는 M개의 숫자 순서대로, '수첩1'에 있으면 1, 없으면 0 출력
입력
첫째 줄에 테스트케이스의 개수 T가 들어온다.
다음 줄에는 ‘수첩 1’에 적어 놓은 정수의 개수 N(1 ≤ N ≤ 1,000,000)이 입력으로 들어온다.
그 다음 줄에 ‘수첩 1’에 적혀 있는 정수들이 N개 들어온다.
그 다음 줄에는 ‘수첩 2’에 적어 놓은 정수의 개수 M(1 ≤ M ≤ 1,000,000) 이 주어지고,
다음 줄에 ‘수첩 2’에 적어 놓은 정수들이 입력으로 M개 들어온다.
모든 정수들의 범위는 int 로 한다.
출력
‘수첩2’에 적혀있는 M개의 숫자 순서대로, ‘수첩1’에 있으면 1을, 없으면 0을 출력한다.
큰 데이터를 빠르게 검색을 해야하니 이진탐색
순서대로 외웠는지 검증하지 않아도 되니까, 걍 '존재'하는지만 봐도 된다. 부품찾기 문제와 비슷한 느낌이구만
어 근데 이거 map 으로 풀면 더 편할듯
map의 in 함수는 o(1)이니까요
파이썬문법공부_집합자료형 / 파이썬 자료형별 메소드의 시간복잡도를 잊지맙시다
import sys
input = sys.stdin.readline
# 입력받기
test_case = int(input())
for _ in range(test_case) :
note_1_num = int(input())
note_1_data = set(map(int, input().split())) # 집합 자료형으로 기록
note_2_num = int(input())
note_2_data = list(map(int, input().split()))
for i in note_2_data :
if i in note_1_data :
print(1)
else :
print(0)
굿굿