문제 출처 : https://www.acmicpc.net/problem/10816

---

문제 파악

가지고 있는 숫자 카드 개수 N, 요소들 N_list가 입력되고

몇개 가지고 있는 지 파악해야 할 수의 개수 M, 요소들 M_list 가 입력되었을 때,

각각 M개의 요소들이 몇개 있는 지 출력하는 문제이다.

N,M 둘다 최대 500,000 이기에 500,000 * 500,000 는 1억을 넘기에 완전탐색(이중 반복문) 으로는 풀이가 불가능하다.

N_list를 단조적으로 정렬할 수 있으므로 이분탐색 알고리즘을 적용가능하다.

이분 탐색 알고리즘의 기본 꼴은 다음과 같다.

def binary_search(arr,target):
	left = 0
    right = len(arr) - 1
    
    while left <= right:
    	mid = (left+right) // 2
        
        if arr[mid] == target:
        	return mid
        
        elif arr[mid] > target:
        	right = mid - 1
            
        else:
        	left = mid + 1
     return 

그러나 이 문제의 경우에는 target이 arr안에 여러개 들어가있을 수 있고 그 개수를 return 해주어야 한다.

target이 여러개 있을 수 있는 경우의 이분탐색은 어떻게 풀 수 있을까

---

예제 입력 1의 경우

N_list 로 6 3 2 10 10 10 -10 -10 7 3 이 입력 받아진다.

이분 탐색의 경우 단조적으로 수열이 정렬되어야 하기에 정렬을 해주면

-10 -10 2 3 3 6 7 10 10 10 이 될 것이다.

이를 통해 같은 값들은 연속된 인덱스를 가짐을 알 수 있다..

그렇다면 이분 탐색을 통해 이 target들의 인덱스를 찾아서, target의 인덱스의 전,후 인덱스를 탐색하며 target과 같다면 count를 계속 늘리는 방식으로 구현하겠다.

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())
N_list = list(map(int,input().split()))

# N_list 정렬
# -10 -10 2 3 3 6 7 10 10 10
N_list.sort()

M = int(input())
M_list = list(map(int,input().split()))

answer = []

def binary_search(arr,target):
    l = 0
    r = len(arr)-1
    idx = -1 # target을 처음 찾은 위치

    while l <= r :
        mid = (l+r) // 2

        if arr[mid] == target:
            idx = mid
            break
        elif arr[mid] > target:
            r = mid - 1
        else:
            l = mid + 1


    # 못 찾았으면 0개
    if idx == -1:
        return 0

    # 2) 양옆으로 퍼지면서 개수 세기
    count = 1  # arr[idx] 하나는 이미 찾았으니까 1부터 시작

    # 왼쪽으로
    i = idx - 1
    while i >= 0 and arr[i] == target:
        count += 1
        i -= 1

    # 오른쪽으로
    i = idx + 1
    n = len(arr)
    while i < n and arr[i] == target:
        count += 1
        i += 1

    return count
for m in M_list:
    answer.append(binary_search(N_list,m))

print(*answer)

답은 잘 나왔지만 python3 의 경우 시간초과가 난다.

왜냐,
이분 탐색은 O(log N) 의 시간복잡도를 가진다.
target과 일치하는 mid를 찾는데 O(log N),
mid를 기준으로 왼쪽 오른쪽 탐색하여야 하기에 O(X)
그리고 질의가 M개 이므로

O(M × (log N + x)) 이 되며
O(log N + X ) = O(N) 으로 볼 수 있어서
O(M*N) 이 되며
최악의 경우 M=N 이 되며 O(N^2) 가 되며 시간 복잡도가 터지게 된다.

---

그래서 이 문제는

1) lower_bound, upper_bound = “양쪽 끝을 이분탐색으로 찾기”

로 풀어야 한다.

lower_bound(target) : target이 처음 나오는 인덱스

upper_bound(target) : target보다 큰 값이 처음 나오는 인덱스

개수 = upper_bound - lower_bound

두 경계를 이분 탐색으로 찾기 때문에 각각 O(log N)
→ 전체 O(M log N) → 통과

import sys
input = sys.stdin.readline

N = int(input())
N_list = list(map(int,input().split()))

# N_list 정렬
# -10 -10 2 3 3 6 7 10 10 10
N_list.sort()

M = int(input())
M_list = list(map(int,input().split()))

def lower_bound(arr,target): # target의 가장 빠른 index 찾기
    left = 0 
    right = len(arr)-1
    lower = len(arr)

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

        if arr[mid] >= target: # target보다 크거나 같은 순간, 즉 target의 인덱스가 처음 나오는 순간 그 인덱스(mid)를 lower 담음
            lower = mid
            right = mid - 1
        else:
            left = mid + 1 

    return lower

def upper_bound(arr, target):
    left, right = 0, len(arr) -1
    upper = len(arr)

    while left <= right:
        mid = (left+right) // 2
        if arr[mid] > target: # target보다 큰 순간, 그 인덱스(mid)를 upper 담음
            upper = mid
            right = mid - 1

        else:
            left = mid+ 1

    return upper

result = []
for m in M_list:
    result.append(upper_bound(N_list,m) - lower_bound(N_list,m))

print(*result)

target이 여러개 있을 때, 그 target의 수를 구할 수 있는.
target의 첫 인덱스와, target 다음 수의 인덱스를 구해 빼서 구할 수 있는 방법을 배운 문제였다.