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

 

일단 이 문제를 보고 for문을 이용해서 모든 점이 선분 내에 있는지 조사해보면 되지 않을까 ? 라고 생각했다

그렇게 코드를 작성하고 제출한 결과 당연히 시간초과 !!

 

ㅋㅋㅎㅋ 이번에도 이분 탐색 관련 문제인 것 같다 ... ^^

내 생각엔 크기를 비교하는 탐색을 해야할때 시간초과를 해결하고 싶으면 이분탐색을 사용하는게 답인 것 같다 !

 

내 코드

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

points = list(map(int, input().split()))
points.sort()

lines = []
for _ in range(m):
    a, b = map(int, input().split())
    lines.append((a, b))
        
def min_binary_search(points, a):
    s = 0
    e = len(points) - 1
    while s <= e :
        mid = (s + e) // 2
        if points[mid] == a:
            return mid
        elif points[mid] > a:
            e = mid - 1
        else:
            s = mid + 1
    return e + 1
    
def max_binary_search(points, b):
    s = 0
    e = len(points) - 1
    while s <= e :
        mid = (s + e) // 2
        if points[mid] == b:
            return mid + 1
        elif points[mid] > b:
            e = mid - 1
        else:
            s = mid + 1
    return e + 1
    
def solution(points, lines):
    for a, b in lines:
        min_idx = min_binary_search(points, a)
        max_idx = max_binary_search(points, b)
        cnt = max_idx - min_idx
        print(cnt)

solution(points, lines)

 

일단 이분 탐색 함수를 작성하는데 선분의 시작 점과 끝 점이 점에서 어느 위치에 있는지 이분 탐색으로 구할 때 서로 다른 방법이 필요한 것 같다.

 

점의 위치가 시작 점 또는 끝 점과 겹칠 때가 있는데 이 점 또한 선분 위에 있는 것이기 때문에 세주어야 한다.

시작점과 겹치는 점까지 세주려면 min_idx 값이 겹치는 점의 인덱스와 같아야 하고 끝 점과 겹치는 점까지 세주려면 max_idx 값이 겹치는 점의 인덱스와 같아야 한다.

왜냐하면 max_idx - min_idx로 겹치는 점의 개수를 셀것이기 때문이다.

그래서 다음과 같이 코드를 작성해 주었다.

왼쪽 코드는 시작점과 겹치는 점이 있는 경우를 위한 코드이고 오른쪽 코드는 끝점과 겹치는 점이 있을 경우를 위한 코드이다.

 

재귀함수를 이용한 이분탐색은 아직 어렵기 때문에 while을 이용해 이분탐색 함수 코드를 작성하였다 .. !

 

이번주 토요일에 오픽을 보는데 오픽을 몇일 미룰까 고민중이다.. 후우우

공부가 너무 부족한 것 같고 자신이 없어서 ㅜㅜㅜ

그리고 내일 꼭 일찍 일어나서 졸업 신청에 대해 문의해봐야지...!!!

오픽만 끝내면 한 숨 돌리는 거니까 열심히 해보자 !!!!!