[이진탐색] 부품찾기

N개의 물건 중에 M개의 물건들이 있는지 확인을 하라.

(1<=N<=1,000,000,1<=M<=100,000)

 

 

입력예시) 

5

8 3 7 9 2

3

5 7 9

 

나의 코드

n=int(input())
arr1=list(map(int,input().split()))
m=int(input())
arr2=list(map(int,input().split()))

for i in range(m):
    left=0
    right=n-1
    while left<=right:
        mid=(left+right)//2
        if arr1[mid]==arr2[i]:
            print("yes",end=' ')
            break
        elif arr1[mid]<arr2[i]:
            left=mid+1
        else:
            right=mid-1
    else:
        print("no",end=' ')

문제의 예시 입력은 간단하여 순차 탐색을 해도 풀수 있지만 N의 입력 가능 범위가 100만 까지 입력이 가능하여 이진 탐색을 사용해서 각각을 찾았다.

초기 right를 n-1로 할지 n으로 할지  while의 left right의 부등호에 =을 포함할지말지 고민하다 디버깅을 통해 위 코드가 나왔다.

 

정답코드(이진탐색)

# 이진 탐색 소스코드 구현 (반복문)
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(가게의 부품 개수) 입력
n = int(input())
# 가게에 있는 전체 부품 번호를 공백을 기준으로 구분하여 입력
array = list(map(int, input().split()))
array.sort() # 이진 탐색을 수행하기 위해 사전에 정렬 수행
# M(손님이 확인 요청한 부품 개수) 입력
m = int(input())
# 손님이 확인 요청한 전체 부품 번호를 공백을 기준으로 구분하여 입력
x = list(map(int, input().split()))

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

M개의 부품을 찾는 최악의 경우 시간복잡도 O(M*logN)의 연산이 필요하므로 이론상 최대 약 200만번의 연산이 이루어진다고 분석할 수 있다.(log1,000,000~ 20)

오히려 N개의 부품을 정렬하기 위해서 요구되는 시간 복잡도는 O(N*logN)이 이론적으로 최대 약 2000만으로 더욱 많은 연산이 필요하다.

결과적으로 이진탐색을 사용하는 문제 풀이방법의 경우 시간 복잡도 O((M+N)*logN)이다.

 

 

정답 코드(계수정렬)

# N(가게의 부품 개수) 입력
n = int(input())
array = [0] * 1000001

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

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

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x:
    # 해당 부품이 존재하는지 확인
    if array[i] == 1:
        print('yes', end=' ')
    else:
        print('no', end=' ')

계수 정렬로 푸니 훨씬 코드 량도 적어지고 직관적으로 굉장히 이해하기 좋은것 같다.

위와같은 풀이도 기억을 해야겠다.