11663 선분 위의 점

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

def find_start(s,e,p,v):
    while s<=e:
        m = (s + e) // 2
        if p[m] >= v :
            e = m-1
        else :
            s = m+1
    return s

def find_end(s, e, p, v):
    while s <= e:
        m = (s + e) // 2
        if p[m] > v:
            e = m - 1
        else:
            s = m + 1
    return e

N,M = map(int,read().split())
points = sorted(list(map(int,read().split())))

for _ in range(M):
    start,end = map(int,read().split())

    find_s = find_start(0, N - 1, points, start)
    find_e = find_end(0, N - 1, points, end)

    print(find_e+1 - find_s)

3. 풀이 및 생각

문제 풀이

선분이 start,end로 주어졌으므로, start와 end가 point들의 위치에서 어디에 있는지를 파악하면 되는 문제이다.

단, end는 주어진 포인트들 중 범위에 만족하는 최대값을 찾고, start는 주어진 포인트들 중 최솟값을 찾는 문제인 것 같다. 따라서 end와 start의 이진탐색 함수의 return 값이 다르다는 것과 조건이 >= 와 <=로 다름을 기억하자.

나의 생각

조금은 start와 end를 return하는 이유에 대해 알게된 것 같기도..? 최솟값을 찾으려면 start를쓰고 최대값을 찾으려면 end를 쓰는게 아닐까 싶다..?