[ 11663 ] [ 이진 탐색 ] 선분 위의 점

문제 설명

---

문제

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

입력

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

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

---

풀이 과정

1. 점들을 오름차순으로 정렬해 준다. => 이진탐색을 하기 위함.
2. 입력받은 선분의 두개의 점을 이진탐색을 진행한다.
   • 파이썬의 bisect_left, bisect_right 함수를 사용한다. 간단하게 설명하자면 bisect_left(x, a)는 a를 x에 삽입할 때, 삽입해야 할 위치를 리턴한다. left와 right의 차이는 왼쪽에 삽입할지, 오른쪽에 삽입할지의 차이이다.
   • 선분의 작은 점은 bisect_left => 작은 점을 포함하게 하기 위해
   • 선분의 큰 점은 bisect_right => 큰 점을 포함하게 하기 위해
   • 위의 두 인덱스 사이에 있는 모든 점들이 선분 안에 포함된다.
3. 점의 개수를 리턴해주면 된다.

---

소스 코드

from bisect import bisect_left, bisect_right
import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
points = list(map(int, sys.stdin.readline().rstrip().split()))
points.sort()

for _ in range(M):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    lidx = bisect_left(points, a)
    ridx = bisect_right(points, b)
    print(ridx - lidx)