[Python] 수 찾기

백준 1920번

문제 설명

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

풀이

이진탐색 문제.
중간점의 값을 찾고 중간점보다 작은 경우 왼쪽 확인, 큰 경우 오른쪽을 확인하는 식으로 시간을 줄일 수 있다. * 그러므로 당연히 sort()는 필수.
엄청 금방 풀고 껌이네ㅋ 하고 있었지만
그 후 나는 런타임 에러(ValueError)의 늪에서 빠져나오지 못하게 된다....

오답

n = int(input())
array_n = list(map(int, input().split()))
array_n.sort()

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

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


for i in array_m:
    result = binary_search(array_n, i, 0, n - 1)

    if result is None:
        print(0)
    else:
        print(1)

도대체 이게 왜 오답인 걸까?
아직도 정확히 모르겠다. array_m과 array_n의 길이가 다를 수도 있어서...?
아무튼 해답은 array_n 배열을 인자로 받지않고 binary_search 안에서 직접 굴리니 해결은 됐다.

제출 코드

n = int(input())
array_n = list(map(int, input().split()))
array_n.sort()

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


def binary_search(target):
    start = 0
    end = n - 1

    while start <= end:
        mid = (start + end) // 2

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


for i in array_m:
    result = binary_search(i)
    
    if result is None:
        print(0)
    else:
        print(1)

찜찜함