[solved.ac 실버3] 11663_선분 위의 점 (파이썬, 이분 탐색)

 

제한 사항

 

문제

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

입력

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

출력

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

예제

 

---

나의 풀이

N과 M이 최대 100,000이 될 수 있으므로 순차적으로 탐색한다면 최악의 상황에 100,000 x 100,000 = 10,000,000,000번의 순회를 해야할 수도 있다

-> 1초에 1억번의 연산을 할 수 있다고 했을 때 100초가 소요된다. 제한 시간인 1초에 한참 못 초과된 수치이다.

그렇기에 이 문제는 이분 탐색으로 접근해야 한다.

선분이 주어지면 입력된 좌표에서 선분에 올라갈 수 있는 좌표가 몇 번 인덱스부터 가능한 지, 몇 번 인덱스까지 가능한 지 찾아야 한다.

주어진 선분의 시작 점과 끝 점을 각각 이분 탐색으로 위치를 찾아보자.

def find(n, points, target):
    start, end = 0, n - 1
    while start < end:
        mid = (start + end) // 2
        if target < points[mid]:
            end = mid - 1
        elif target > points[mid]:
            start = mid + 1
        else:
            return mid
    return start

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

for _ in range(m):
    s, e = map(int, input().split())

    # find s's index
    result = find(n, points, s)
    si = result if points[result] >= s else result + 1

    # find e's index
    result = find(n, points, e)
    ei = result if points[result] <= e else result - 1

    print(ei - si + 1)

find라는 이분 탐색 함수로 가장 근접한 값을 찾아낸다.

그리고 시작 점이 결과보다 작거나 같게, 끝 점은 결과보다 크거나 같게 해야 선분 위의 좌표를 커버할 수 있다.

이렇게 찾은 인덱스를 빼서 1을 더하면 개수를 구할 수 있다.

 

채점 결과

첫 번째 시도:

치사하게 좌표들을 정렬되지 않은 테스트 케이스도 존재했나보다. 이분 탐색을 활용할 때는 반드시 정렬된 상태에서 해야한다.

두 번째 시도:

파이썬 기본 input() 메서드로 했더니 시간 초과가 났다.

import sys
input = sys.stdin.readline

위 코드를 추가해 빠른 입력을 받자.