이진탐색 - 예제)부품찾기

문제 이해

핵심) 손님이 요청한 부품번호가 리스트에 있으면 yes, 없으면 no

input ex)
내가 가지고 있는 것
N = 5
[8,3,7,9,2]
손님이 찾는 것
M = 3
[5,7,9]

input 조건)
정수 1<=N<=1,000,000
정수 1<=M<=1,000,000

책 풀이

다량의 데이터 검색은 이진탐색 알고리즘이 효율적이다

1) N개의 데이터를 정렬시킨다
2) 데이터 중 손님이 찾는게 존재하는지 이진탐색을 수행한다. (총 M번)

이 경우의 시간복잡도

이진탐색 : O(M logN) ➡️ 약 2000만번 (log1,000,000 ≈ 20)
N개 데이터 정렬 : O(NlogN) ➡️ 약 200만번 연산

최종 시간복잡도 : O((M+N)logN)

기본 풀이

손님이 찾는 m개의 target이 존재하는지
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())
data = list(map(int, input().split()))
m = int(input())
targets = list(map(int, input().split()))

data.sort() # 이진 탐색을 수행하기 위한 사전 정렬!!!!

# 손님이 확인 요청한 부품 번호를 하나씩 확인 
for target in targets :
  # 해당 부품이 존재하는지 확인
  result = binary_search(data, target, 0, n-1)

  if result != None : print('yes', end = ' ')
  else              : print('no', end =' ')

계수 정렬 활용 풀이

모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만든 뒤,
리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인한다.

계수정렬의 복잡도는 O(N)이지만 메모리 낭비를 야기할 수 있다.
다음의 링크를 참고하자

# 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=' ')
  

집합 자료형 활용 풀이

set()함수는 집합 자료형을 초기화할때 사용한다.
집합 자료형은 단순히 특정 데이터가 존재하는지 검사할 때 효과적이다.

파이썬문법공부_집합자료형

파이썬 자료형별 메소드의 시간복잡도

set 자료형의 containment(이게 존재하느냐. in 활용)의 복잡도는 O(1)이다 개쩐다!!!
list의 containment 복잡도는 O(N)이니까 비교하면 혁쉰 호호..

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=' ')

세가지 풀이가 있는데..

위의 세가지 방법 모두 효과적으로 풀 수 있는 방법이다!