[코테]99클럽 코테 스터디 3일차 TIL 백준 11663 선분 위의 점

https://www.acmicpc.net/problem/11663

해당 문제는 앞선 두 문제와 마찬가지로 이분탐색 문제이다! 문제를 보자마자 이분탐색인 것을 깨달았던 것이, 어떤 값이 어떤 리스트에서 어떤 위치를 차지하는지? 에 대한 문제였기 때문에 바로 알아차릴 수 있었다. 

처음 풀이는 공간 메모리 초과 오류가 떴는데, 그 이유는 주어진 선분의 처음과 끝을 for문으로 길게 늘린다음 해당 점이 그 안에 포함되어 있는지 이분탐색으로 찾았기 때문이였다. 

import sys

read = sys.stdin.readline

N, M = map(int, read().split())

coord = list(map(int, read().split()))

lines = []

for _ in range(M):

    lines.append(list(map(int, read().split())))

def bisection(target, data):

    start = 0

    end = len(data) - 1

    while start <= end:

        mid = (start + end) // 2

        if target == data[mid]:

            return mid

        elif target > data[mid]:

            start = mid + 1

        else:

            end = mid - 1

    return

for line in lines:

    data = [i for i in range(line[0],line[-1] + 1)]

    cnt = 0

    for coor in coord:

        if bisection(coor, data) is not None:

            cnt += 1

    print(cnt)

 

이 문제로 인해 bisect 모듈을 사용하면서, 선분의 처음과 끝을 각각 target 값으로 잡고 정렬된 점의 좌표 안에 선분의 처음과 끝 값이 포함되는지 확인하는 방식으로 바꾸었더니 통과하였다.

import sys

from bisect import bisect_left, bisect_right

read = sys.stdin.readline

N, M = map(int, read().split())

coord = list(map(int, read().split()))

lines = []

for _ in range(M):

    lines.append(list(map(int, read().split())))

coord.sort()

for line in lines:

    start, end = line[0], line[1]

    left_idx = bisect_left(coord, start)

    right_idx = bisect_right(coord, end)

    print(right_idx - left_idx)