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

11663번: 선분 위의 점

 

문제

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

입력

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

출력

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

코드

• bisect 라이브러리 활용

import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right

n, m = map(int, input().split())
dot = sorted(list(map(int, input().split())))

for _ in range(m):
    start, end = map(int, input().split())
    print(bisect_right(dot, end) - bisect_left(dot, start))

• 직접 이분 탐색 구현

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dot = sorted(list(map(int, input().split())))

def bs(arr, target, lr):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if target < arr[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return left if lr == 0 else right

for _ in range(m):
    start, end = map(int, input().split())
    print(bs(dot, end, 1)-bs(dot, start, 0)+1)

 

• bs() 함수
  : 이분탐색을 하며 배열에서 target과 근접한 위치를 찾는다. lr은 target과 일치하는 값이 없을 때 target과 가장 가까운 값 중 target보다 작은 값을 리턴할지 큰 값을 리턴할지 결정하는 파라미터이다.
  • target이 arr[mid]의 값이 더 작다면 arr에서 더 작은 값, 즉, 인덱스가 더 작은 값으로 가야하므로 right를 mid - 1으로 갱신해준다. 그렇지 않다면 인덱스가 더 큰 값으로 가야하므로 left를 mid + 1으로 업데이트해준다.

 

이 문제는 편의상 이분탐색으로 분류해서 넣어뒀지만 파라메트릭 서치 문제이다. 

 

파라메트릭 서치(Parametric Search)

: 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것

• 파라메트릭 서치를 이용하여 문제를 풀 수 있는 경
  • 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우
  • (최솟값을 구하는 경우) 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족
  • (최댓값을 구하는 경우) 최댓값이 x라면, x이하의 값에 대해서는 모두 조건을 만족

 

[참고]

[이분탐색] 파라메트릭 서치(개념)