[SWEA/Python] 5207. 이진탐색

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

1. 문제를 이해 못해서 한참 헤맸다!
   오른쪽 - 왼쪽을 번갈아서 탐색한다는 말은 결국 '오-오-왼', '왼-왼-오' 와 같이 같은 방향을 연속으로 탐색할 수 없다는 말이었다.
2. 코드는 기본 이진 탐색 코드에 같은 방향을 연속으로 탐색하는 경우만 제외하도록 설정해줬다.
   before 변수를 만들어서 그 전에 왼쪽/오른쪽 중 어떤 그룹을 선택했는지 표시하고 같은 방향을 연속으로 선택했다면 바로 -1을 리턴해줬다.
3. 리턴 값이 -1이 아닌 경우만 카운팅해주면 끝!

 

📌 코드

import sys
sys.stdin = open('input.txt')

def binary_search(arr, target):
    global before

    left = 0
    right = N - 1

    while left <= right:
        middle = (left + right) // 2

        if arr[middle] == target:
            return middle
        elif arr[middle] > target:
            if before == 'left':
                return -1

            right = middle - 1
            before = 'left'
        else:
            if before == 'right':
                return -1

            left = middle + 1
            before = 'right'
    
    return -1


T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    A.sort()
    cnt = 0

    for target in B:
        before = ''

        idx = binary_search(A, target)

        if idx != -1:
            cnt += 1

    print('#{} {}'.format(t, cnt))