나의 풀이
n = int(input())
nArray = list(map(int, input().split()))
m = int(input())
mArray = list(map(int, input().split()))
answer = list()
s, e = 0, n-1
def binarySearch(arr, target, start, end):
if end >= start:
mid = (end + start) // 2
if arr[mid] == target:
answer.append('yes')
elif arr[mid] > target:
binarySearch(arr, target, start, mid-1)
else:
binarySearch(arr, target, mid+1, end)
else:
return answer.append('no')
for i in range(m):
binarySearch(nArray, mArray[i], s, e)
for ans in answer:
print(ans, end=' ')
정답
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())
array = list(map(int, input().split()))
array.sort()
m = int(input())
x = list(map(int, input().split()))
for i in x:
result = binary_search(array, i, 0, n - 1)
if result != None:
print('yes', end=' ')
else:
print('no', end=' ')
정답을 보고나니 이진 탐색은 작은 인덱스에는 작은 값이 인덱스가 높아지면 큰 값이 저장 되여 있다는 전제가 깔려야
해당 함수가 올바르게 작동한다. 하지만 나는 정렬하는 것을 까먹었다. 하지만 테스트케이스에서는 문제가 발생하지 않아서 잘 모르고 있었다.
n = int(input())
array = [0] * 1000001
for i in input().split():
array[int(i)] = 1
m = int(input())
x = list(map(int, input().split()))
for i in x:
if array[i] == 1:
print('yes', end=' ')
else:
print('no', end=' ')
위와 같이 계수정렬로 풀수도 있다.
또한 아래와 같이 집합 해결할 수 있다.
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=' ')