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

난이도 : Silver 3
Link : https://www.acmicpc.net/problem/11663
Tag : 이분탐색, 정렬
풀이일자 : 2024년 9월 22일

📌 문제 탐색하기

N : 점의 개수
M : 선분의 개수
grid : 점 좌표

본 문제는 주어진 점과 선분에서 시작점과 끝점이 주어졌을 때 주어진 점이 몇개 있는지 구하는 문제이다.

가능한 시간복잡도

주어진 점을 정렬하는 시간O(nlogn)
M개의 선분을 이분 탐색으로 처리하는 시간 O(mlogn)
따라서 전체적인 시간복잡도는 nlogn + mlogn 이다.

📌 문제 접근 방법

먼저 주어진 점의 좌표를 정렬하여 이분탐색 할 수 있는 상태로 만들 것이다.
그리고 매번 주어지는 시작점과 끝점의 위치를 탐색하기 위해 이분탐색을 도입할 것이다.
이분탐색을 통해 시작점과 끝점에서 포함되는 점의 개수를 출력하면 끝이다.

📌 코드 설계하기

1. n,m을 입력받는다.
2. grid를 입력받고 정렬한다.
3. find_start 이분탐색 함수를 만든다.
   • start = 0으로 초기화
   • end = n-1로 초기화 하여 시작과 끝의 인덱스를 나타낸다.
   • while start <= end 를 통해 시작점과 끝 인덱스가 작거나 같을때 까지 진행한다.
   • mid 중간 인덱스를 (start+end)//2 를 통해 지정한다.
   • if grid[mid]<a 라면 a값이 중간값보다 큼으로 start의 값을 mid+1로 지정한다.
   • 그렇지 않다면 a값이 mid값보다 작으므로 end = mid-1로 지정한다.
   • while문이 끝나면 end+1를 return한다.
     (끝날때 가르키고 있는 start값은 a보다 크거나 같은 첫번째 값의 위치를 가르키게 되고 end값은 start+1의 값을 가지고 있기 때문이다.)
4. find_start 이분탐색 함수를 위와 같이 만든다.
5. m번 동안 a,b를 입력받아 find_end - find_start를 한뒤 +1을 해줘 점의 개수를 구한다.

📌 시도 회차 수정 사항

1. 틀렸습니다. (시간초과)
   input를 사용했을때 시간초과가 발생하였다. import sys를 통해 시간초과를 해결했다.

📌 정답 코드

import sys
n,m = map(int, sys.stdin.readline().split()) #n:점 m:선분 개수
grid = list(map(int, sys.stdin.readline().split()))
grid = sorted(grid)

def find_start(a):
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2
        if grid[mid] < a:
            start = mid + 1
        else:
            end = mid - 1
    return end + 1

def find_end(b):
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2
        if grid[mid] > b:
            end = mid - 1
        else:
            start = mid + 1
    return end

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