부품 찾기 [이진 탐색]

이진 탐색

n=int(input())
array1=list(map(int,input().split())) # 가게의 부품
m=int(input())
array2=list(map(int,input().split())) # 손님의 부품
array1.sort()  # 이진 탐색하기 위해 사전 정렬

def binary_search(array,target,start,end):
    while start<=end:
        mid=(start+end)//2
        if array[mid]==target:
            return mid
        elif array[mid]<target:
            start=mid+1
        else:
            end=mid-1

    return None


for i in array2:
    if binary_search(array1,i,0,len(array2))==None:
        print('no',end=' ')
    else:
        print('yes',end=' ')

• 다량의 정렬된 데이터 검색은 이진 탐색이 가장 효과적. O(logn)
• 이진탐색 시작 전에는 꼭 sort() 함수를 통해 데이터 정렬을 해줘야 함.

계수 정렬

n=int(input())
array=[0]*1000001

# 가게에 있는 전체 부품 번호 기록
for i in input().split():
    array[int(i)]+=1

# 손님 부품 개수, 부품번호
m=int(input())
x=list(map(int,input().split()))

for i in x:
    if array[i]==1:
        print('yes',end=' ')
    else:
        print('no', end=' ')

• 부품 번호의 입력 범위에서 리스트를 만들고 계수 정렬 활용

집합 자료형 이용

n=int(input())

array=set(map(int,input().split()))

# 손님의 부품 개수, 부품 번호
m=int(input())
x=list(map(int,input().split()))

for i in x:
    if i in array:
        print('yes',end=' ')
    else:
        print('no', end=' ')

• 집합 자료형을 사용 시, 데이터가 자동으로 정렬됨.
• 단순 특정 데이터가 존재하는 지 검사 시 매우 유용함.