boj 11663 : 선분 위의 점

문제 주소: https://www.acmicpc.net/problem/11663

난이도: silver 3

1.문제설명

• 일차원 좌표상의 점들의 리스트가 주어진다.
• 이때 선분의 시작점과, 끝점이 주어졌을 때
• 선분안에 몇개의 점들이 포함되는지 개수를 구하여라

2.문제해결 아이디어.

• 선분의 시작점보다 크거나 같은 점 중 가장 작은 점의 인덱스를 구하고(left)
• 선분의 끝점보다 작거나 같은 점 중 가장 큰 점의 인덱스를 구해서(right)
• right - left + 1해주면된다.
• 이제 인덱스를 어떻게 구할까? -> 선형탐색으로는 시간초과 날 것
• 이진탐색으로

3.문제접근법

• 함수를 2개만들었다.
• left, right의 인덱스를 각각 리턴해준다.
• 이분탐색으로 구현했다.
• 아 일단 이진탐색을 하려면 정렬이 되어있어야한다.

def finding_left(a,b,dots):
    #a보다 크거나 같은 가장작은 원소의 인덱스
    if a <= dots[0]: #선분의 시작지점이 가장 작은 원소보다 왼쪽이면
        return 0 #시작 인덱스는 0임
    else: #이진탐색
        start = 0 #인덱스의 시작값 0
        end = len(dots)-1#인덱스의 끝값
        while start <= end:
            mid = (start + end)//2
            if a <= dots[mid] <= b: #mid인덱스에 해당하는 점이 선분에 있으면
                end = mid - 1 #가능한 점 중 가장 작은 점의 인덱스 구해야하기 때문에
            else:
                if dots[mid] < a: #mid인덱스에 해당하는 점이 선분의 시작보다 작다면
                    start = mid + 1#탐색범위의 시작포인트를 오른쪽으로 이동시킨다(키워준다)
                elif dots[mid] > b: #mid인덱스에 해당하는 점이 선분의 끝보다 크다면
                    end = mid - 1 #탐색범위의 끝 포인트를 왼쪽으로 이동시킨다(작게한다)
    return start

def finding_right(a, b, dots):
    #b보다 작거나 같은 가장 큰 원소의 인덱스
    if b >= dots[-1]:  # 선분의 시작지점이 가장 작은 원소보다 오른쪽이면
        return len(dots)-1  # 마지막 인덱스 return
    else:
        start = 0
        end = len(dots) - 1
        while start <= end:
            mid = (start + end) // 2
            if a <= dots[mid] <= b:
                start = mid + 1
            else:
                if dots[mid] < a:
                    start = mid + 1
                elif dots[mid] > b:
                    end = mid - 1
    return end

4.특별히 참고할 사항

• 이진탐색을 두번써야 하는점이 신선(?)했고
• 아직 이진탐색의 결과로 어떤걸 return 해야하는지 햇깔릴때가 있다.
• 논리적으로 조금 더 생각하며 정리해볼 필요가 있다.

5.코드구현

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dots = list(map(int, input().split()))
dots.sort()

def finding_left(a,b,dots):
    #a보다 크거나 같은 가장작은 원소의 인덱스
    if a <= dots[0]: #선분의 시작지점이 가장 작은 원소보다 왼쪽이면
        return 0 #시작 인덱스는 0임
    else:
        start = 0
        end = len(dots)-1
        ans = 0
        while start <= end:
            mid = (start + end)//2
            if a <= dots[mid] <= b:
                end = mid - 1
            else:
                if dots[mid] < a:
                    start = mid + 1
                elif dots[mid] > b:
                    end = mid - 1
    return start

def finding_right(a, b, dots):
    #b보다 작거나 같은 가장 큰 원소의 인덱스
    if b >= dots[-1]:  # 선분의 시작지점이 가장 작은 원소보다 오른쪽이면
        return len(dots)-1  # 시작 인덱스는 0임
    else:
        start = 0
        end = len(dots) - 1
        while start <= end:
            mid = (start + end) // 2
            if a <= dots[mid] <= b:
                start = mid + 1
            else:
                if dots[mid] < a:
                    start = mid + 1
                elif dots[mid] > b:
                    end = mid - 1
    return end

for i in range(M):
    a, b = map(int,input().split())
    left_idx = finding_left(a,b, dots)
    right_idx = finding_right(a,b, dots)
    print(right_idx- left_idx + 1)