백준 1920( 수 찾기 ) - Python(파이썬)

1) 이진탐색으로 하지 않은 코드

시간 초과난 코드: 

import sys

sys.stdin.readline() #필요 없으므로 그냥 명시
A = list(map(int,sys.stdin.readline().split()))
sys.stdin.readline() #필요 없으므로 그냥 명시
B = list(map(int,sys.stdin.readline().split()))
for i in B:
    if i in A:
        print(1)
    else:
        print(0)

 

list -> set으로 변경

import sys

sys.stdin.readline() #필요 없으므로 그냥 명시
A = set(map(int,sys.stdin.readline().split()))
sys.stdin.readline() #필요 없으므로 그냥 명시
B = list(map(int,sys.stdin.readline().split()))
for i in B:
    if i in A:
        print(1)
    else:
        print(0)

list의 search는 O(n)이고, 처음부터 값이 나올 때까지 순차탐색하는 방식

set의 search는 O(1)이고, 탐색이 필요 없이 바로 search가 완료되는 방식

 

파이썬 자료구조들의 여러 method의 time complexity

TimeComplexity - Python Wiki

---

2) 이진탐색으로 한 코드

이진탐색에 대한 설명

이진탐색- 순차 탐색, 이분탐색/이진탐색, 이진탐색트리

2-1) 재귀함수 쓰지 않고 while문 사용

import sys

sys.stdin.readline() #필요 없으므로 그냥 명시
A = list(map(int,sys.stdin.readline().split()))
A.sort() #이진탐색을 위해 정렬 1 2 3 4 5 이렇게 명시
sys.stdin.readline() #필요 없으므로 그냥 명시
B = list(map(int,sys.stdin.readline().split()))
def binary_search(array,target,start,end):
    while start<=end:
        mid=(start+end)//2
        if array[mid]==target:
            return True
        elif array[mid]>target:
            end=mid-1
        else:
            start=mid+1
    return None

for i in B:
    result = binary_search(A, i, 0, len(A)-1)
    if result==None:
        print(0)
    else:
        print(1)

2-2) 재귀함수 사용

import sys

sys.stdin.readline() #필요 없으므로 그냥 명시
A = list(map(int,sys.stdin.readline().split()))
A.sort() #이진탐색을 위해 정렬 1 2 3 4 5 이렇게 명시
sys.stdin.readline() #필요 없으므로 그냥 명시
B = list(map(int,sys.stdin.readline().split()))
def binary_search(array,target,start,end):
    if start>end:
        return None
    mid=(start+end)//2
    if array[mid]==target:
        return True
    elif array[mid]>target:
        return binary_search(array,target,start,mid-1)
    else:
        return binary_search(array,target,mid+1,end)

for i in B:
    result = binary_search(A, i, 0, len(A)-1)
    if result==None:
        print(0)
    else:
        print(1)