[백준] 11663. 선분 위의 점 (Python)

백준 문제 풀이 - 이진탐색

📰 문제

---

문제 확인 🏃

💡 입출력 예제

---

5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8

>> 3
2
4
2
0

5 2
5 6 7 8 9
1 2
11 12

>> 0
0

💬 풀이

---

🎵 첫번째 풀이

import sys

input = sys.stdin.readline
N, M = map(int, input().split())            # 점의 개수 N, 선분의 개수 M
dots = list(map(int, input().split()))      # 점의 좌표

def binary_min(start, end, target):
    
    while start <= end:
        mid = (start + end) // 2

        if dots[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return end+1

def binary_max(start, end, target):

    while start <= end:
        mid = (start + end) // 2

        if dots[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1

    return end


dots.sort()
for _ in range(M):
        start, end = map(int, input().split())
        print(binary_max(0, N-1, end) - binary_min(0, N-1, start) + 1)

🎵 두번째 풀이

import sys

input = sys.stdin.readline
N, M = map(int, input().split())            # 점의 개수 N, 선분의 개수 M
dots = list(map(int, input().split()))      # 점의 좌표

def binary_min(start, end, target):
    
    while start <= end:
        mid = (start + end) // 2

        if dots[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return start

def binary_max(start, end, target):

    while start <= end:
        mid = (start + end) // 2

        if dots[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1

    return end


dots.sort()
for _ in range(M):
        start, end = map(int, input().split())
        print(binary_max(0, N-1, end) - binary_min(0, N-1, start) + 1)

✒️ 생각

---

문제를 잘 읽자! 어디에도 점이 정렬되어 입력된다는 말은 없다!