1seul357

[SWEA] 이진 탐색 본문

알고리즘/SWEA

[SWEA] 이진 탐색

1seul 2021. 11. 28. 16:07
T = int(input())
for TC in range(T):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    count = 0
    A.sort()

    for i in range(M):    # B의 크기(M)만큼 반복
        tmp = B[i]
        l = 0             # l의 초기값 설정 
        r = len(A) - 1    # r의 초기값 설정
        mid = (l + r) // 2   # 중간값 설정
        flag = -1         # 왼쪽, 오른쪽 번갈아가면서 탐색하는지 확인하는 flag 초기화
        while l <= r:     # l이 r보다 작은 동안 반복
            if tmp == A[mid]:   # 값을 찾았다면
                count += 1      # count += 1
                break           # 반복문 종료
            elif tmp < A[mid] and flag != 0: # 중간보다 작고, 바로 전에 왼쪽을 체크한게 아니라면 
                r = mid - 1        # r값 바꾸기
                mid = (l + r) // 2  # 중간값 바꾸기
                flag = 0  
            elif tmp > A[mid] and flag != 1: # 중간보다 크고, 바로 전에 오른쪽 체크한게 아니라면
                l = mid + 1
                mid = (l + r) // 2
                flag = 1
            else:    # 같은 구간을 두번 연속 체크하면
                break   # 반복문 종료

    print('#{} {}'.format(TC+1, count))

'알고리즘 > SWEA' 카테고리의 다른 글

[SWEA] 격자판의 숫자 이어붙이기  (0) 2021.11.28
[SWEA] 장훈이의 높은 선반  (0) 2021.11.28
[SWEA] 정사각형 방  (0) 2021.11.28
[SWEA] 그룹 나누기  (0) 2021.11.28
[SWEA] 최소 이동 거리  (0) 2021.11.28