thdwldud_

<문제>
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
시간 제한 1초

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

💡문제 해결 아이디어

• 알고리즘에 이분탐색이 있지만 후에 알고리즘 공부 후 다시 해당 방법으로 풀 예정
• 이번에는 간단하게 set으로 만들어 탐색하는 풀이 사용
  • list를 사용할 경우 시간초과 발생
    • list의 in 연산자를 통한 포함 여부의 시간 복잡도는 O(n)
    • set, dictionary의 in 연산을 통한 포함 여부의 시간 복잡도는 O(1) 
  • 해당 집합에 포함되는지 여부만 확인하면 되므로 set 자료형을 사용

n = int(input())
a = set(map(int, input().split())) # 시간복잡도를 고려하여 set자료형 사용

m = int(input())
array = list(map(int, input().split()))

for num in array:
    print(1) if num in a else print(0)