[백준] 11663번 선분 위의 점 (파이썬)

11663번: 선분 위의 점

 

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력 

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

---

코드 

import sys

n, m = map(int, sys.stdin.readline().split())
dot = list(map(int, sys.stdin.readline().split()))
dot.sort()


def dot_min(a):  # 선분 중 가장 작은 점 구하기 
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2

        if dot[mid] < a:
            start = mid + 1
        else:
            end = mid - 1
    return end + 1


def dot_max(b):   # 선분 중 가장 큰 점 구하기
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2

        if b < dot[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return end


for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(dot_max(b) - dot_min(a) + 1)

 

풀이 

전체적인 로직은 매우 간단하다.

• 선분 중 가장 큰 점의 인덱스와 작은 점의 인덱스를 구하면 된다. (점의 좌표는 미리 정렬해야 함)
  • 만약 점이 [1, 3, 10, 20, 30]이고 선분은 3 ~ 30일때→ 이 경우 점의 개수는 4 - 1 + 1 이 될 것이다. (점의 인덱스 위치로 계산해야 함)
  • 선분 중 가장 작은 점은 3 (인덱스 1)이고, 가장 큰 점은 30 (인덱스 4)이다. 

 

로직은 간단한데 이걸 이분탐색으로 구현해낼 때 좀 시간이 걸렸다... 

다 짜고 나니 어디서 헤맸던 건지.. 괜한 시간을 낭비한 거 같기도 .. ㅋㅋ ㅠ