99클럽 코테 스터디 3일차 TIL + 백준 11663 선분 위의 점 (파이썬)

※ 11663 선분 위의 점

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

문제 해결 TIP

이분 탐색 변형 문제이다. 처음에 for문으로 돌렸을 때는 역시 시간 초과..아래 입력 함수도 유용하게 써야겠다.

import sys

N, M = map(int,sys.stdin.readline().split())
dot = list(map(int,sys.stdin.readline().split()))

 

전체 코드

import sys

N, M = map(int,sys.stdin.readline().split())
dot = list(map(int,sys.stdin.readline().split()))
dot.sort()

def dot_min(start_dot):
    start = 0
    end = N - 1
    while start <= end:
        mid = (start + end) // 2
        if start_dot > dot[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return end + 1

def dot_max(end_dot):
    start = 0
    end = N - 1
    while start <= end:
        mid = (start + end) // 2
        if end_dot >= dot[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return end

for i in range(M):
    count = 0
    start_dot, end_dot = map(int,sys.stdin.readline().split())
    print(dot_max(end_dot)-dot_min(start_dot)+1)

---

• 비기너 문제 : 문자열 반복 https://www.acmicpc.net/problem/2675
• 미들러 문제 : 선분 위의 점 https://www.acmicpc.net/problem/11663
• 챌린저 문제 : 네트워크 복구 https://www.acmicpc.net/problem/2211