99클럽 코테 스터디 3일차 TIL Boj 11663. 선분 위의 점

Approach

• N, M 둘 다 100,000이기 때문에, N^2을 넘어서는 안된다고 생각
• 처음에는 선분 a, b 를 start, end로 잡고 리스트를 돌면서 이분탐색해보려했는데, 생각해보니 이렇게 하면 N^2이었다.
• 차라리 선분 a, b 각각을 리스트에서 해당 인덱스를 찾고 개수를 반환해야겠다고 생각함
• 리스트 원소 내에서 자기보다 큰 원소들 중에 가장 앞, 작은 원소들 중에 가장 뒤 인덱스를 찾는 거였기 때문에 upper bound, lower bound를 생각했다.
• bisect에서 이것을 지원하지만, 직접 구현해보았다.

---

Solution 💡

import sys

def min_search(num):

    start = 0
    end = len(lst) - 1
    while start <= end:
        mid = (start + end) // 2

        if lst[mid] < num:
            start = mid + 1
        else:
            end = mid - 1

    return end + 1

def max_search(num):

    start = 0
    end = len(lst) - 1
    while start <= end:
        mid = (start + end) // 2

        if lst[mid] > num:
            end = mid - 1
        else:
            start = mid + 1

    return end

N, M = map(int, sys.stdin.readline().split())

lst = list(map(int, sys.stdin.readline().split()))
lst.sort()

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    print(max_search(b) - min_search(a)+1)