[11663] 선분 위의 점 in python

 

> 이분 탐색

https://www.acmicpc.net/problem/11663

11663번: 선분 위의 점

 

이분 탐색 문제를 풀 때마다 헷갈렸던 거!

left, right 값에 인덱스를 넣어야할 때도 있고,

0,max(array)처럼 0과 배열의 최댓값을 넣어줘야 풀리는 문제도 있었다.

 

근데 언제 인덱스를 넣어야하는지, 최댓값을 넣어줘야하는지

기준이 잡히지 않아서 헤맸던 문제다.

---

 

<정리>

1. 문제에서 값을 구하라고 하는 문제 

> 배열의 최댓값을 right에 넣어줌.

left=0

 

2. 문제에서 배열의 범위를 구하라고 하느냐

또는 배열의 범위를 기준으로 값을 구해내느냐

> 인덱스 값을 left,right에 넣어준다.

 

---

일단 

아래 링크의 문제(랜선 자르기)에서는

배열의 값을 넣어줬다. (인덱스 x)

이 문제에서는 최대의 랜선의 길이를 구하라는 문제.

즉 범위가 아닌 값을 구하라는 문제였기에

배열의 최댓값을 right에 넣어줬던 것이다.

 

이분탐색 중에서도

parametric search라는 문제에 해당한다고 한다.

(궁금증을 해결해주신 지인님의 깨알 피드백, +_+)

 

https://eboong.tistory.com/492

[1654] 랜선 자르기 in python

 

 

그러나 선분 위의 점에서의 문제는

각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지를 구하는 문제로,

값이 아닌

해당 범위내에 존재하는 점의 개수니까

인덱스를 기준으로 움직여야한다.

 

따라서 

이 문제에선 left=0, right=len(array)-1을 넣어서

진행해줘야한다.

 

import sys

n, m = map(int, sys.stdin.readline().split())
dot = sorted(list(map(int, sys.stdin.readline().split())))
for _ in range(m):
    left = 0
    right = n - 1
    x, y = map(int, sys.stdin.readline().split())
    while left <= right:
        mid=(left+right)//2
        if dot[mid] < x:
            left =mid+1
        else:
            right=mid-1
    firstIdx=left
    left,right=0,n-1
    while left<=right:
        mid=(left+right)//2
        if dot[mid]>y:
            right=mid-1
        else:
            left=mid+1
    endIdx=right+1
    print(endIdx-firstIdx)