백준 10815 파이썬 숫자 카드 문제 시간초과 해결 이진탐색

쉬운 줄 알았는데..

시간 초과 오류가 났다!! 

 

이유는? in탐색은 하나하나 다 하기에 시간 복잡도가 O(n)이 걸려 오래걸린다 

따라서 시간 복잡도를 줄여야함 

 

이진 탐색을 이용하자 

 

이진 탐색이란? 

중간값을 값과 비교하고 왼쪽 오른쪽 이동해가면서 구하는 거

 

이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

 

위키백과에서 가져온 정의 

 

N=int(input()) 
str1=list(map(int, input().split(' ')))
str1.sort()

M=int(input())
str2=list(map(int, input().split(' ')))


arr = [0 for i in range(M)]
count=0
        
for i in str2:
    l=0
    r=N-1
    while(l<=r):
        mid=int((l+r)/2)
        if str1[mid]==i:
            arr[count]=1
            break
        elif str1[mid] < i:
            l=mid+1
        else:
            r=mid-1
    count+=1

print(*arr)

 

map함수란? 파이썬 내장 함수로 각 요소에 특정한 함수를 적용시킬 때 쓴다. 주로 여러 가지 값을 입력받을 때 사용함

print(*arr)은 *을 붙이며 , (쉼표)등을 빼고 원소만을 출력해준다