부품 찾기

나의 풀이

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=' ')