[Python] 11663번 선분 위의 점

✏️ 문제

 

문제 파악

(큰 인덱스 - 작은 인덱스)를 출력해서 문제를 풀었는데

선분의 시작점이나 끝점이 점의 좌표와 같을 때 예상 값보다 1개씩 작게 나오는 문제가 있었다..

그래서 시작점이나 끝점 중 하나를 원래 인덱스 값보다 -1 해서 계산하면 출력이 잘 나오긴 한다...

근데 뭔가 야매로 푼 거 같아서 찝찝 ㅠ 했는데 다른 정답코드를 찾아보니 이런 식으로 나눠서 푸는 게 맞는 것 같다! 휴

 

알고리즘

• 정렬
• 이분 탐색

 

 

코드

import sys
input = sys.stdin.readline

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

def bs(ary, l, switch):
  start, end = 0, n-1
  i = -1

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

    if ary[mid] <= l:
        i = (mid - 1 if switch == 1 and ary[mid] == l else mid)
        start = mid + 1
    else:
        end = mid - 1

  return i

for i in range(m):
  l1, l2 = map(int, input().split())
  i1, i2 = 0, 0
  i1 = bs(point, l1, 1)
  i2 = bs(point, l2, 2)
  print(i2 - i1)