[SWEA][D3][#11893] 분할정복_이진탐색

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

서로 다른 정수 N개가 주어지면 정렬한 상태로 리스트 A에 저장한다. 그런 다음 리스트 B에 저장된 M개의 정수에 대해 A에 들어있는 수인지 이진 탐색을 통해 확인하려고 한다.

전체 탐색 구간의 시작과 끝 인덱스를 l과 r이라고 하면, 중심 원소의 인덱스 m=(l+r)//2 이고, 이진 탐색의 왼쪽 구간은 l부터 m-1, 오른쪽 구간은 m+1부터 r이 된다.

이때 B에 속한 어떤 수가 A에 들어있으면서, 동시에 탐색 과정에서 양쪽구간을 번갈아 선택하게 되는 숫자의 개수를 알아보려고 한다.

다음은 10개의 정수가 저장된 리스트 A에서 이진 탐색으로 6을 찾는 예이다.

그림 생략

예를 들어 10을 찾는 경우 오른쪽-오른쪽 구간을 선택하므로 조건에 맞지 않는다

5를 찾는 경우 m에 위치하므로 조건에 맞는다.

이때 m에 찾는 원소가 있는 경우 방향을 따지지 않는다. M개의 정수 중 조건을 만족하는 정수의 개수를 알아내는 프로그램을 만드시오.

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 A와 B에 속한 정수의 개수 N, M이 주어지고, 두 줄에 걸쳐 N개와 M개의 백만 이하의 양의 정수가 주어진다.

1<=N, M<=500,000

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

예제

입력

3
3 3
1 2 3
2 3 4
3 5
1 3 5
2 4 6 8 10
5 5
1 3 5 7 9
1 2 3 4 5

출력

#1 2
#2 0
#3 3

My Sol

# 합병정렬
def MS(arr):
    def MSS(low, high):
        if high - low < 2:
            return

        mid = (low+high) // 2
        MSS(low, mid)
        MSS(mid, high)
        MSM(low, mid, high)
        return arr

    def MSM(low, mid, high):
        tmp = []
        l, h = low, mid
        while l < mid and h < high:
            if arr[l] < arr[h]:
                tmp.append(arr[l])
                l += 1
            else:
                tmp.append(arr[h])
                h += 1

        while l < mid:
            tmp.append(arr[l])
            l += 1
        while h < high:
            tmp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = tmp[i-low]

    return MSS(0, len(arr))


# 이분 탐색
def BS(s, e, t, f):
    while s <= e:
        m = (s+e)//2
        if t == SA[m]:
            return 1
        elif t > SA[m]:
            if f > 0: return 0
            s = m+1
            f = 1
        else:
            if f < 0: return 0
            e = m-1
            f = -1
    return 0


# 실행
T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    SA = MS(A)
    B = list(map(int, input().split()))

    cnt = 0
    for b in B:
        cnt += BS(0, N-1, b, 0)

    print(f'#{tc} {cnt}')

합병정렬을 이용해 입력을 정렬하고, 이분 탐색 함수를 작성하여, 해당 리스트에 찾으려는 값이 있는지 확인하였다. 이 과정에서 flag의 f 변수를 두어, mid를 기준으로 큰 쪽의 리스트 구간인지, 작은 쪽의 리스트 구간인지를 표시하여 인자로 넘겨 확인했다.

만약 이전의 f와 같다면 번갈아가며 선택하는 것이 아니므로 0을 return하고, 번갈아가던 중에 mid의 인덱스와 같은 값을 발견한다면 리스트 내에 찾으려는 값이 있는 것이므로 1을 반환한다.

전역변수 cnt에 함수의 반환값을 더하면 규칙을 준수하며 값을 찾아낸 경우 1을 더하고 그것이 아니라면 0을 더하여 결과를 출력하게 된다.

결과

PASS