알고리즘_코딩테스트/이것이 코딩테스트다
[이진탐색] 부품찾기
논곰
2021. 12. 7. 23:10
1. 문제 설명
- 부품 리스트의 배열과 찾는 부품에 해당하는 두 배열이 주어지고, 부품 리스트에 찾는 부품이 있는지를 확인하는 문제
2. 코드
# 입력
N = int(input())
array1 = list(map(int, input().split()))
array1.sort()
M = int(input())
array2 = list(map(int, input().split()))
array2.sort()
"""
5
8 3 7 9 2
3
3 9 7
"""
# 이진탐색
def binary_search(array, target, start, end):
mid = (start+end)//2
if start > end:
return None
if array[mid]==target:
return True
elif target < array[mid]:
return binary_search(array, target, start, mid-1)
else:
return binary_search(array, target, mid+1, end)
# 출력
def parts(N, array1, M, array2):
for i in array2:
result = binary_search(array1, i, 0, N-1)
if result != None:
print("yes", end=" ")
else:
print("no", end= " ")
parts(N, array1, M, array2)
# >> yes yes yes
3. 코멘트
- in을 사용해서 문제를 풀 수도 있어보인다. 하지만 더 큰 데이터가 주어질 때 더 수월하게 찾을 수 있기에 binary_search로 구현한 것 같다.
- binary_search는 재귀적으로 구현된다는 점을 기억하자.