[백준 11663번] 파이썬 - 선분 위의 점

백준 11663 - 선분 위의 점

시간 제한 1초, 메모리 제한 256MB

# 조건

• 일차원 좌표상의 점 N개와 선분 M개가 주어진다.
• 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다.
• 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

# 접근 방법

• 주어지는 좌표가 10억 이하이므로 각 점을 리스트에 기록하며 값을 더하는 것은 시간, 메모리적으로도 말이 안된다.
• 따라서, 주어진 점을 오름 차순으로 정렬해준 후 이분 탐색을 활용해준다.
• 주어지는 선분의 시작점이 들어가는 곳을 찾고, 끝 점이 들어가는 곳을 찾아서 두 곳의 차를 구하면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from bisect import bisect_left, bisect_right  

N, M = map(int, input().split())  
points = list(map(int, input().split()))  
points.sort()  

for _ in range(M):  
    st, en = map(int, input().split())  
    start = bisect_left(points, st)  
    end = bisect_right(points, en)  
    print(end - start)