5207. 파이썬 SW 문제해결 구현 4일차 - 이진 탐색

태그 잊지 않고 붙이세요
#sw_expert_academy #binary_search #D3 #Solved
문제 링크

제한사항

• 1<=N, M<=500,000
• 1<=t<=50

문제 정리

이분 탐색 과정 중에 왼쪽 오른쪽을 번갈아 검색한 경우의 개수를 구해라.

접근 방법

단순한 이분 탐색 구현 문제다. 단, flag 값을 통해서 이전에 왼쪽을 탐색했는지 혹은 오른쪽을 탐색했는지 판별하면 된다.
A가 정렬이 필요하므로 NlogN이 필요하고 추가적으로 M개 원소를 이진 탐색하므로 M*logN이 필요하다.

복잡도

시간복잡도: 정렬 + M개 원소를 이진탐색 = O(N * logN) + O(M * logN) = O(N * logN + M * logN) = O((N + M) * logN)
공간복잡도: O(N + M)

코드

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    # B에 숫자가 A에 없으면 통과 처리 아님
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    B = list(map(int, input().split()))

    answer = 0
    for target_num in B:
        left = 0
        right = len(A) - 1
        flag = 0 # 왼쪽이면 -1 오른쪽이면 1
        while left <= right:
            mid = (left + right) // 2
            if A[mid] == target_num:
                answer = answer + 1
                break
            elif A[mid] > target_num:
                if flag == -1:
                    break
                else:
                    flag = -1
                    right = mid - 1
            elif A[mid] < target_num:
                if flag == 1:
                    break
                else:
                    flag = 1
                    left = mid + 1
    print(f"#{test_case} {answer}")