[SWEA] 5207_이진 탐색

📕 문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

💡 풀이법

: 일반적인 이진 탐색에 조금 이상한 특징을 넣어놓은 문제였다. 뭔가 문제 설명이 친절하지 않았고 굳이..? 싶었다

 

* 가능한 경우

1. 바로 찾는 경우

2. 오른쪽 한번 가고 바로 찾는 경우, 왼쪽 한번 가고 바로 찾는 경우

3. 오왼오왼 번갈아가면서 보다가 찾는 경우

 

즉, 오오나 왼왼이 나오면 바로 그 경우는 걸러야한다.

그래서 오른쪽 갔다가 오른쪽 한번 더 가면 바로 break를 걸어줘야 한다. (왼쪽의 경우도 동일)

이 경우를 분류해주기 위해 flag라는 변수를 만들었다.

flag를 왼쪽 오른쪽 두개 만들었다가 바로 시간초과남,,, 딱 하나만 만들어야 한다^^

 

def binary_search(arr, target):
    global ans
    left = 0
    right = N - 1

    flag = -1
    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            ans += 1
            return
        elif arr[mid] > target:
            if flag == 0:
                break
            right = mid - 1
            flag = 0

        else:
            if flag == 1:
                break
            left = mid + 1
            flag = 1


T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    nums = list(map(int, input().split()))
    find_nums = list(map(int, input().split()))
    nums.sort()
    ans = 0
    for i in find_nums:
        binary_search(nums, i)
    print('#{} {}'.format(tc, ans))