[알고리즘] 백준 파이썬 11663 선분 위의 점

📍 문제 탐색하기

선분 위의 점 문제는 1차원 좌표 상의 N개의 점과 M개의 선분이 주어졌을 때,
각 선분에 속하는 점의 개수를 빠르게 구하는 문제이다.
점의 좌표와 선분의 시작점, 끝점이 주어지며, 점의 좌표는 중복되지 않는다.

---

문제 조건

• 점의 개수 N: 1≤N≤100,000
• 선분의 개수 MMM: 1≤M≤100,000
• 점의 좌표: 서로 중복되지 않으며, 1≤xi≤1,000,000,000
• 선분의 시작점과 끝점: 1≤li,ri≤1,000,000,000

---

출력 조건

• 각 선분마다 포함된 점의 개수를 한 줄에 하나씩 출력한다.

---

가능한 시간 복잡도

• N,M이 최대 100,000이므로 단순한 선형 탐색을 수행할 경우 O(N×M)으로 비효율적이다.
• 효율적인 탐색을 위해 이분 탐색을 사용하면 O(Nlog⁡N+Mlog⁡N)로 해결 가능하다.

---

📍 코드 설계하기

1. 점 정렬
   • 입력으로 주어진 점들을 오름차순 정렬한다.
   • 이후 이분 탐색을 통해 특정 구간에 속하는 점들을 빠르게 찾는다.
2. 이분 탐색으로 선분 처리
   • 각 선분의 범위 [l,r]에 대해:
     • 시작점 lll 이상인 첫 번째 위치를 찾기 위해 bisect_left 사용.
     • 끝점 rrr 이하인 마지막 위치를 찾기 위해 bisect_right 사용.
     • 두 위치의 차이를 구하면 해당 범위 내의 점 개수를 얻을 수 있다.
3. 결과 출력
   • 선분마다 포함된 점 개수를 출력.

---

📍 시도 회차 및 수정 사항

1. 초기 구현
   • 리스트를 순회하면서 각 선분의 시작과 끝 사이의 점 개수를 직접 계산 (비효율적 → 시간 초과 발생).
2. 이분 탐색 적용
   • Python의 bisect 모듈을 활용해 선분 범위 내 점 개수를 빠르게 찾도록 최적화.

---

📍 코드 구현

import sys
from bisect import bisect_left, bisect_right

input = sys.stdin.readline

# 입력 받기
N, M = map(int, input().split())
points = sorted(map(int, input().split()))  # 점들을 오름차순 정렬

# 각 선분에 대해 계산
results = []
for _ in range(M):
    l, r = map(int, input().split())
    
    # l 이상인 첫 번째 위치 찾기
    left_index = bisect_left(points, l)
    # r 이하인 마지막 위치 찾기
    right_index = bisect_right(points, r)
    
    # 범위 내 점 개수
    results.append(right_index - left_index)

# 결과 출력
sys.stdout.write("\n".join(map(str, results)) + "\n")

---