Baekjoon_11663 - 선분 위의 점
문제
일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.
출력
입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.
해결방법
- 주어진 선분과 점을 각각 반복문을 사용해 비교하기엔 시간복잡도가 O(NM) 으로 시간초과가 날것 같아 다른 방법을 생각해야 했다.
- 따라서 이분 탐색을 이용해 점의 좌표들 중에서 선분의 시작점과 끝점을 각각 찾아 그 사이에 있는 점들 개수를 찾는 방법을 생각해 보았다.
- 예제 입력 1을 예로 들면, 점 좌표인 [1, 3, 10, 20, 30] 을 이분 탐색의 범위로 잡고, 선분 (1, 10) 의 시작점과 끝점인 1과 10을 각각 이분 탐색을 이용해 찾는 것이다. 시작점에서 이분탐색 결과의 left 와 끝점에서 이분탐색 결과의 right 차이 + 1이 점의 개수가 된다.
코드
import sys
input = sys.stdin.readline
n,m = map(int, input().split())
point = list(map(int, input().split()))
point.sort()
def find_min(findNum):
left = 0
right = n-1
while left <= right:
mid = (left + right) // 2
if point[mid] < findNum:
left = mid + 1
else:
right = mid - 1
return left
def find_max(findNum):
left = 0
right = n-1
while left <= right:
mid = (left + right) // 2
if point[mid] > findNum:
right = mid -1
else:
left = mid + 1
return right
for i in range(m):
lineL, lineR = map(int, input().split())
print(find_max(lineR) - find_min(lineL) + 1)이분탐색을 두번 써야 하는 문제라 이분탐색 부분을 함수로 빼보려 했지만,
if문 부분의 범위 설정에서 등호 여부가 달라서 따로 빼기엔 더 복잡해질것 같아서 하지 않았다.
