[ SW Expert Academy ] 5207. 이진탐색

1차 시도. [ 4 / 10 ] Fail

뭐지... 뭔데... ?? !!?? 왜 틀리는데... 

def binary_search(arr, target, start, end):
    mid = (start+end)//2

    if end < start:
        return 0
    if arr[mid] == target:
        return arr[mid]
    elif target <= arr[mid]:
        return binary_search(arr, target, start, mid-1)
    elif arr[mid] < target:
        return binary_search(arr, target, mid+1, end)


if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T + 1):
        a, b = map(int, input().split())
        n = list(map(int, input().split()))
        m = list(map(int, input().split()))
        n.sort()
        answer = 0
        for target in m:
            if binary_search(n, target, 0, len(n)-1):
                answer += 1

        print("#" + str(test_case), answer)

 

얘야.. 문제 똑바로 읽어라...

' 동시에 탐색 과정에서 양쪽구간을 번갈아 선택하게 되는 숫자의 개수를 알아보려고 한다. ' 

그냥 정답 찾아지는 개수가 아니라 이런 조건을 만족하는 숫자의 개수!

 

참.. 너무하게도 테케에는 저 조건이 안 걸리게 제시되어 있다.. 너무해여 ~ ><

 

 

2차 제출. [10 / 10] PASS

문제 이해가 조금 어려웠다. 양쪽구간을 번갈아 선택한다는게, 그냥 왼 / 오 한 번씩 방문만 하면 된다는 건 줄 알았는데 매 탐색이 왼쪽, 오른쪽이어야 했다.

prev를 global값으로 선언하게 구현했었는데 답이 제대로 안 나왔다.. 왜,.? 이유 모르겠다 ㅠㅜㅜㅡ

결과적으로 안 돼서 매개변수로 이전 값 참조하게 수정했더니 바로 패스.. 흠 .. 

def binary_search(arr, target, start, end, prev):
    mid = (start+end)//2

    if end < start:
        return 0
    if arr[mid] == target:
        return arr[mid]
    elif target <= arr[mid]:
        if prev == 'left':
            return 0
        prev = 'left'
        return binary_search(arr, target, start, mid-1, prev)
    elif arr[mid] < target:
        if prev == 'right':
            return 0
        prev = 'right'
        return binary_search(arr, target, mid+1, end, prev)

if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T + 1):
        a, b = map(int, input().split())
        n = list(map(int, input().split()))
        m = list(map(int, input().split()))
        prev = None
        n.sort()
        answer = 0
        for target in m:
            if binary_search(n, target, 0, len(n)-1, prev):
                answer += 1

        print("#" + str(test_case), answer)