[Algorithm🧬] 코딩 인터뷰 완전 분석 : 숫자 카운팅

배열에 오름차순으로 N개의 숫자가 저장되어 있다. M개의 탐색할 숫자가 주어질 때, 각 숫자가 배열에 몇 개씩 저장되어 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N 이 입력된다. (1≤N≤200,000)
둘째 줄에 배열에 저장 되어있는 N개의 숫자가 순서대로 공백으로 구분되어 입력된다.
셋째 줄에 M 이 입력된다. (1≤M≤200,000)
넷째 줄에 M개의 탐색할 숫자가 순서대로 공백으로 구분되어 입력된다.
(이 숫자는 정렬 되어있지 않다)

10
1 1 1 6 9 11 13 17 19 20
2
1 9

출력

입력 넷째 줄에서 주어진 탐색할 숫자의 배열 내 저장된 개수를 차례대로 출력한다.

3 1

해당 숫자를 하나 서치해서 찾고,
그 숫자 앞 뒤로 같은 숫자가 있으면 개수를 늘려가는 식으로 탐색했다.

import sys

def binary_search(start, end, find, arr):
    if start > end:
        return -1

    mid = (start + end) // 2

    if arr[mid] == find:
        return mid
    elif arr[mid] < find:
        return binary_search(mid + 1, end, find, arr)
    else:
        return binary_search(start, mid - 1, find, arr)

def search_front_back(index, arr, find):
    count = 0
    length = len(arr)
    back_index = index + 1
    while index > -1 and arr[index] == find:
        index -= 1
        count += 1

    while back_index < length and arr[back_index] == find:
        back_index += 1
        count += 1

    return count

# 입력 처리
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

find_n = int(sys.stdin.readline())
find_arr = list(map(int, sys.stdin.readline().split()))

for i in range(find_n):
    # 이진 탐색으로 해당 숫자 위치 찾고
    index = binary_search(0, n - 1, find_arr[i], arr)
    # 양 옆에 같은 숫자 탐색
    count = search_front_back(index, arr, find_arr[i])
    print(count, end=' ')

2회차

해당 숫자 중 제일 작은 것과 해당 숫자 중 제일 큰 것을 찾아서 갯수 카운트

전에 풀었던 방법은 최악의 경우 log n + n 인데
이 방법은 log n + log n

def min_binary(find):
    left = 0
    right = N - 1

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

        if arr[mid] == find:
            index = mid
            right = mid - 1
        elif arr[mid] > find:
            right = mid - 1
        else:
            left = mid + 1

    return index

def max_binary(find):
    left = 0
    right = N - 1

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

        if arr[mid] == find:
            index = mid
            left = mid + 1
        elif arr[mid] > find:
            right = mid - 1
        else:
            left = mid + 1

    return index


for find in find_arr:
    index = min_binary(q)
    if index != -1:
        print(max_binary(q) - index + 1, end=' ')
    else:
        print(0, end=' ')