부품 찾기

📌문제

동빈이네 전자매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

 

📌풀이

다량의 데이터 검색은 이진 탐색 알고리즘을 이용해 효과적으로 처리

 

N개의 부품을 번호 기준으로 정렬

이후 M개의 찾고자 하는 부품이 정렬한 리스트에 존재하는지 확인

 

이진 탐색은 정렬 되어 있어야만 사용 가능

 

📌코드

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


# 가게의 부품 개수 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백으로 구분하여 입력
array = list(map(int, input().split()))
array.sort()  # 정렬

# 손님이 확인 요청한 부품 개수 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백으로 구분하여 입력
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 array에 존재하는지 확인
    result = binary_search(array, i, 0, n - 1)
    if result != None:
        print("yes", end=" ")
    else:
        print("no", end=" ")

 

부품을 찾는 과정에서 최악의 경우 시간 복잡도 O(M x logN)

정렬에서 시간 복잡도 O(N x logN)

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬