BaekJoon 11663번: 선분 위의 점 (Python)

---

1. Problem

---

2. Solution

import bisect
import sys

N, M = map(int, sys.stdin.readline().split())
xcoords = list(map(int, sys.stdin.readline().split()))
xcoords.sort()
for i in range(M):
    amin, amax = map(int, sys.stdin.readline().split())
    left = bisect.bisect_left(xcoords, amin)
    right = bisect.bisect_left(xcoords, amax)
    if len(xcoords) <= right or xcoords[right] != amax:
        right -= 1
    print(right - left + 1)

---

3. Detail

N개의 점이 주어지고, 일차원 좌표상의 M개의 선분이 주어진다. 이때, 각각의 선분 내에 포함되어있는 점이 주어진 N개의 점 중 몇개인지를 구하는 문제이다.

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

점의 갯수와 선분의 갯수를 입력받아 각각 N과 M 변수에 할당한다.

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

일차원 좌표상의 점의 좌표 N개를 입력받아 xcoords라는 변수에 할당한다.

xcoords.sort()

선분의 min과 max값의 좌우 값의 index를 이용하여 문제를 풀 것이기 때문에 xcoords list 내의 값들을 정렬해준다.

for i in range(M):
    amin, amax = map(int, sys.stdin.readline().split())
    left = bisect.bisect_left(xcoords, amin)
    right = bisect.bisect_left(xcoords, amax)
    if len(xcoords) <= right or xcoords[right] != amax:
        right -= 1
    print(right - left + 1)

선분이 M개 있으므로 for문은 M번 반복되어야 한다. 각각의 선분의 시작점과 끝점을 입력받아 amin과 amax라는 변수에 할당한다. bisect.bisect_left(xcoords, amin) 함수를 이용하여 xcoords list가 정렬된 순서를 유지하도록 amin이 삽입될 index를 찾아 left 변수에 할당한다. bisect.bisect_left(xcoords, amax)도 마찬가지로 amax가 삽입될 index를 찾아 right 변수에 할당한다. 하지만 여기서 left index 값과 right index 값을 그대로 이용하면 안되기 때문에 if문을 사용해야 한다. 만약 xcoords list의 길이가 right index의 값보다 작거나 같거나 또는 xcoords list의 right index의 값이 amax와 다르다면 right index의 값을 1만큼 빼주어야 한다. 이는 각각 len(xcoords)와 right가 같다면 right index에 해당하는 값은 선분 내의 점이 아니기 때문이고, 또한 amax와 xcoords[right]의 값이 같다면 선분 내에 포함되는 점이되고, 값이 다르다면 xcoords[right]는 선분 내에 포함되는 점이 아니기 때문이다. 마지막으로 left와 right 사이의 값의 갯수를 구하되 left와 right를 포함한 갯수를 구해야하기 때문에 right - left + 1을 출력한다.

---

* Point!
Python에서 upperbound(초과), lowerbound(이상) 개념을 사용하기 위해 bisect.bisect_left() 함수를 이용