[이코테 Ch7-2] 부품 찾기 (이진 탐색)

👩🏻‍💻문제설명

[이코테 Ch7-2] 부품 찾기 (이진 탐색)

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

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

N=5
[8, 3, 7, 9, 2]

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M=3
[5, 7, 9]

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다. 구분은 공백으로 한다.

입력

• 첫째 줄에 정수 N이 주어진다. (1<=N<=1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.
• 셋째 줄에는 정수 M이 주어진다. (1<=M<=100,000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 10억 이하이다.

출력

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

입력 예시

5
8 3 7 9 2
3
5 7 9

출력 예시

no yes yes

✍️Idea Sketch

알고리즘 : 이진 탐색

시간복잡도

정렬과 이진 탐색의 연산을 합한 총 시간복잡도는 O((M + N)logN) 이다.

파이썬은 기본 정렬 라이브러리인 sorted()와 sort()함수를 제공한다. 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적인 경우 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다. 따라서 가게의 부품을 정렬하는 데에 시간복잡도는 O(NlogN)이다.

또한 이진 탐색 알고리즘의 시간복잡도는 O(logN)이며, 이진 탐색을 손님이 신청한 부품 개수인 M번 만큼 실행한다. 따라서 이진 탐색 연산의 시간복잡도는 O(MlogN)이다.

따라서 정렬과 이진 탐색의 연산을 합한 총 시간복잡도는 O((M + N)logN) 이다.

✍️내 소스코드

• 가게의 물품 배열 store을 sorted()로 정렬한다.

• bisect 라이브러리를 사용하여 store에서 손님이 요구한 물품 x를 삽입할 위치 인덱스를 반환한다.

• 해당 인덱스의 물품이 손님이 요구한 물품 x와 동일하면 yes, 그렇지 않으면 no를 출력한다.

• 참고사이트 : Python 이진 탐색 라이브러리 Doc

  import sys
  import bisect
  si = sys.stdin.readline

  n = int(si())
  store = sorted(map(int, si().split()))
  m = int(si())
  wish = list(map(int, si().split()))

  for x in wish:
    idx = bisect.bisect_left(store, x)

    if store[idx] == x:
      print('yes', end = ' ')
    else:
      print('no', end = ' ')