이코테 chapter 07 이진 탐색 - 부품 찾기

문제

동빈이네 전자 매장에는 부품이 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를 출력한다.

 

접근법 & 풀이 (의식의 흐름)

1. 딱히 생각해볼 필요도 없이 순차탐색이나 이진탐색을 사용해서 풀면되는 문제라 바로 풀었다.

 

 

소스 코드

# 순차 탐색으로 문제 해결
def search(array, target):
  for i in range(len(array_1)):
    if array[i] == target:
      return "yes"
  
  return "no"

n = int(input())
array_1 = list(map(int, input().split()))

m = int(input())
array_2 = list(map(int, input().split()))

for i in array_2:
  print(search(array_1, i), end = ' ')

# 이진 탐색으로 문제 해결
def binary_search(array, target, start, end):
  if start > end:
    return "no"
  
  mid = (start + end) // 2

  if array[mid] == target:
    return "yes"
  
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  
  else:
    return binary_search(array, target, mid + 1, end)


for i in array_2:
  print(binary_search(array_1, i, 0, n - 1), end = ' ')

오답노트 & 알아낸 것

- 일단 책에 있는 소스코드를 보면서 재귀함수말고 반복문으로도 구현할 수 있다는 걸 배웠다. 앞으로 문제를 풀면서 좀 더 나한테 맞는 거로 적용해나가면 될거같다.... 그리고 변수명좀 잘 지어야겠다 ㅠㅠ

- in, not in 연산자가 아직은 익숙치가 않아서 막상 써야할 때에 잘 못쓰는거같다.. 하오;;;;