BOJ - 11663

백준 문제 링크
선분 위의 점

❓접근법

1. 선분의 시작점과 끝점을 나눌 것이다.
   점의 좌표를 리스트 dot으로 받아주고 정렬한다.
2. search_min 함수를 만들어 기본 이분 탐색 코드에서
   dot[mid]가 선분의 시작점(x)보다 크거나 같으면 end = mid - 1
   dot[mid]가 선분의 시작점(x)보다 작으면 start = mid + 1
   마지막엔 end + 1을 return하면 된다.
3. search_max 함수를 만들어 기본 이분 탐색 코드에서
   dot[mid]가 선분의 끝점(y)보다 작거나 같으면 start = mid + 1
   dot[mid]가 선분의 끝점(y)보다 크면 end = mid - 1
   마지막엔 end를 return하면 된다.
4. 그럼 인덱스를 구했으므로 search_max - search_min + 1 을 반환하면
   가능한 점의 개수를 구할 수 있다.

👌🏻코드

import sys
N, M = map(int, sys.stdin.readline().split())

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

dot.sort()

def search_min(x):
    start = 0
    end = N-1
    
    while start <= end:
        mid = (start + end) // 2
        
        if dot[mid] < x:
            start = mid + 1
            
        else:
            end = mid - 1
            
    return end + 1
            

def search_max(y):
    start = 0
    end = N-1
    
    while start <= end:
        mid = (start + end) // 2
        
        if y < dot[mid]:
            end = mid - 1
            
        else:
            start = mid + 1
            
    return end

for _ in range(M):
    x, y = map(int, sys.stdin.readline().split())
    
    print(search_max(y) - search_min(x) + 1) # 인덱스의 차이 + 1