9주차_#2776 암기왕

문제 이해 💬

'수첩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)