백준 1920 : 수 찾기 with 파이썬

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

1. 이중for문으로 할 경우 시간초과   cf. 10^3 ≒ 2^10 

n=int(input())
nums=list(map(int, input().split()))
m=int(input())
tlist=list(map(int, input().split()))

for t in tlist:
    ch=0
    for num in nums:
        if t==num:
            print(1)
            ch=1
            break  		#ch를 통한 스위치가 없으면 break시에도 밑으로 내려가 print(0) 출력
    if ch==0:
        print(0)

 

2. 정렬(NlogN)을 이용해 빠르게 값 찾기

n=int(input())
nums=list(map(int, input().split()))
m=int(input())
tlist=list(map(int, input().split()))

nums.sort()   # 이진탐색을 위해 정렬하기

def search(st, end, target):  # st, end는 인덱스이고, target은 값
    if st==end:
        if nums[st]==target:
            print(1)
            return
        else : 
            print(0)
            return
    
    mid=(st+end)//2
    if nums[mid] < target:
        search(mid+1, end, target)
    else :
        search(st, mid, target)

for t in tlist:
    search(0, n-1, t)