부품 찾기

 

유형 분석 및 구현

이 문제는 이진탐색 또는 계수 정렬을 통해 풀 수 있다.

 

조건은 다음과 같다.

N = 최대 백만

정수의 범위는 백만이하이다.

M = 최대 10만

 

예를 들어, 이 문제를 순차적 탐색으로 해결한다고 가정하면

시간 복잡도는 log(M*N)이다.

N(앞에서부터 하나하나 확인해가면 찾으려는 값일 때, 끝냄)

M(찾으려는 값 수)

최악의 경우 1조회의 연산이 필요하다.

 

하지만 이진탐색으로 해결시

우선 정렬이 필요한데, 파이썬의 정렬의 연산수는 NlogN이다.

이 후 이진탐색으로 해결시 M개의 데이터에 대해 총 MlogN이다.

결과적으로 시간 복잡도는 O((N+M)logN)이다.

굉장히 작아짐을 알 수 있다.

 

"연산 계산시 조건에 맞추어 풀 수 없다는 것을 직감한다면 바로 이진탐색을 사용하자."

 

계수 정렬을 사용하면

우선, 만든 체크리스트에 값을 set해야 한다. 파이썬에서 set은 O(1)이다. O(N)

이후, 찾으려는 값을 리스트에서 get한다 파이썬에서 get은 O(1)이다. O(M)

결과적으로 O(N+M)이 시간 복잡도가 된다.

 

 

코드

# 이진탐색
n = 5
products = [8, 3, 7, 9, 2]
products.sort()
m = 3
find = [5, 7, 9]

def binary_search(length, i):
    min_index = length[0]
    max_index = length[1]
    if min_index > max_index:
        return False
    mid_index = (min_index + max_index)//2
    if i == products[mid_index]:
        return True
    elif i < products[mid_index]:
        return binary_search([min_index, mid_index-1], i)
    elif i > products[mid_index]:
        return binary_search([mid_index+1, max_index], i)


for i in find:
    result = binary_search([0, n], i)
    if not result:
        print("no", end=" ")
        continue
    print("yes", end=" ")
print(" ")




# 계수 정렬
n = 5
products = [8, 3, 7, 9, 2]
products.sort()
check = [0]*11
m = 3
find = [5, 7, 9]

for product in products:
    check[product] = 1
for i in find:
    if check[i] == 1:
        print("yes", end=" ")
    else:
        print("no", end=" ")
print(" ")