99클럽 코테 스터디 _ 3일차 TIL (이분탐색, Bisect)

 

< 문제 >

[백준] 11663. 선분 위의 점 / 실버3

---

< 풀이 >

코드 변수 정의

• lidx : 선분(line)의 시작점(left)이 리스트(points)에서 추가될 수 있는 위치의 인덱스 값
• ridx : 선분(line)의 끝점(right)이 리스트(points)에서 추가될 수 있는 위치의 인덱스 값 + 1
• points : N개의 좌표상의 점
• lines : M개의 선분

---

Binary Search
시간복잡도 : O(N*logN + M*logN)
     - points.sort : O(N * logN)
     - M개 선분을 binary_search : O(M * logN)            *bisect : O(logN)

from bisect import bisect_left, bisect_right

def binary_search(points, line):
    left, right = line
    lidx = bisect_left(points, left)
    ridx = bisect_right(points, right)
    return ridx - lidx

def f():
    N, M = map(int, input().split())
    points = list(map(int, input().split()))
    points.sort()
    lines = [list(map(int, input().split())) for _ in range(M)]
    
    for line in lines:
        print(binary_search(points, line))
        
f()

 

• 좌표상의 점 N개를 points에 리스트로 담고 이를 정렬한다.
• 선분 M개를 lines에 담고 각 선분에 대해 binary_search로 선분 위 점의 개수를 구한다.
  • 선분의 시작점이 points에 들어갈 위치를 반환하여 lidx를 구한다.
  • 선분의 끝점이 points에 들어갈 위치를 반환하여 ridx를 구한다.
  •  

---

< 회고 >

binary_search 함수 내에서 lidx, ridx를 구할 때, bisect 라이브러리를 사용할 수 있다는 것을 뒤늦게 알았다..

 

 

Bisect
: 정렬된 리스트에 특정 원소 삽입 후 다시 정렬할 필요가 없도록 하는 파이썬 라이브러리

• bisect_left(list, x, lo = 0, hi = len(list))
  • x가 list에 이미 있는 경우, 삽입 위치는 기존 항목 앞(왼쪽)이 된다.
  • 반환된 삽입 지점 i에 대해  →  (왼쪽) all(val < x for val in list[lo : i])  |  (오른쪽) all(val >= x for val in list[i : hi])
• bisect_right(list, x, lo = 0, hi = len(list))
• bisect(list, x, lo = 0, hi = len(list))
  • x가 list에 이미 있는 경우, 삽입 위치는 기존 항목 뒤(오른쪽)가 된다.
  • 반환된 삽입 지점 i에 대해  →  (왼쪽) all(val <= x for val in list[lo : i])  |  (오른쪽) all(val > x for val in a[i : hi])
• 예시

import bisect

a = [1, 3, 10, 20, 30]

lines = [[1, 10], [20, 60], [2, 15]]

for line in lines:
    left, right = line
    lidx = bisect.bisect_left(a, left)
    ridx = bisect.bisect_right(a, right)    # bisect.bisect(a, right)
    print(f'lidx  : {lidx}  /  ridx  : {ridx}')

# 출력값
lidx  : 0  /  ridx  : 3
lidx  : 3  /  ridx  : 5
lidx  : 1  /  ridx  : 3

 

 

---

참고

bisect - https://docs.python.org/ko/3.10/library/bisect.html