[이진 탐색] 이코테 (파이썬) 부품 찾기 풀이

[문제]

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의

 

부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개

 

종류를 모두 확인해서 경적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

 

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

 

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

 

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

 

M = 3
[5, 7, 9]

 

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

[입력 조건]

1. 첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)

 

2. 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

 

3. 셋째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)

 

4. 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

 

[출력 조건]

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

<입력 예시>
5
8 3 7 9 2
3
5 7 9
<출력 예시>
no yes yes

 

[풀이]

def binary_search(arr, target, start, end) :
  while start <= end :
    mid = (start+end) // 2

    if arr[mid] == target :
      return mid
    elif arr[mid] > target :
      end = mid - 1
    else :
      start = mid + 1
  return None

n = int(input())
arr = list(map(int, input().split()))
m = int(input())
search = list(map(int, input().split()))

arr.sort()

for i in search :
  result = binary_search(arr, i, 0, n-1)
  if result == None :
    print('no', end=' ')
  else :
    print('yes', end=' ')

 

먼저 정수 n을 입력받고 리스트 형식으로 n개의 정수를 공백으로 구분하여 입력받아 arr에 할당한다.

 

또한, 정수 m을 입력받고 리스트 형식으로 m개의 정수를 공백으로 구분하여 입력받아 search에 할당한다.

 

이진 탐색은 기본적으로 이미 정렬된 배열에서 사용하기 때문에 arr를 오름차순으로 정렬한다.

 

정렬을 수행한 다음에는 손님이 확인 요청한 부품 번호를 하나씩 확인하는데, binary_search( ) 메소드에 데이터들을

 

전달하여 해당 부품이 존재하는지 확인하여 최종 결과를 출력한다.

 

binary_search( ) 메소드에서는 반복문을 수행하여 해당 부품이 존재한다면 해당 인덱스(중간점 인덱스)를 반환하고

 

만약 중간점의 값보다 찾고자 하는 값이 작은 경우에는 왼쪽을, 중간점의 값보다 찾고자 하는 값이 큰 경우에는

 

오른쪽을 확인할 수 있도록 한다.

 

추가적으로 이진 탐색 예제를 재귀적으로 구현한 코드와 반복문을 사용하여 구현한 코드는 아래 게시물에서 확인할 수 있다.

 

https://unie2.tistory.com/210?category=878713 

[파이썬] 순차 탐색과 이진 탐색

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저