11663. [Python]선분 위의 점

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 256MB
• 이분 탐색

 

3. 파이썬 코드

 

import sys
# 많은 인풋 처리
input = sys.stdin.readline
# N 과 M 인풋
N, M = map(int,input().split())
# 점들 리스트
num_list = list(map(int,input().split()))
# 점들 정렬
num_list.sort()
# M 선분 횟수만큼 반복
for _ in range(M):
    # 시작점 끝점 받기
    start,end = map(int,input().split())
    # 시작점과 끝점이 범위내에 없는 경우 연산 제외
    if start > num_list[-1] or end < num_list[0]:
        print(0)
        continue
    # lower bound 부분에서 인덱스 체크
    left_point = 0
    # upper bound 부분에서 인덱스 체크
    right_point = 0
    # 시작점 끝점 설정
    left = 0
    right = N-1
    # 이분 탐색 진행하며 lower bound 체크
    while left <= right:
        middle = (left+right)//2

        if num_list[middle] >= start:
            left_point = middle
            right = middle - 1
        else:
            left = middle + 1
    # 시작점 끝점 초기화
    left = 0
    right = N - 1
    # upper bound 체크
    while left <= right:
        middle = (left+right)//2

        if num_list[middle] <= end:
            right_point = middle
            left = middle + 1
        else:
            right = middle - 1
    # 인덱스 이므로 upper bound - lower bound + 1 해줌
    print(right_point - left_point + 1)

 

4. 문제를 풀고난 후 생각

 

• 이분 탐색을 진행하기 위해 점들에 대해서 정렬을 우선 해주고 시작했다.
• N, M 값이 100,000 이므로 많은 인풋 처리를 위해 import sys 를 선언해주었고, 이후 이분 탐색을 진행함에 있어서 Lower bound 영역과 Upper bound 영역으로 나누어 오른쪽 점의 최대값 위치와 왼쪽 점의 최소값 위치를 체크하여 두 인덱스의 차를 출력해주었다.
• +1 을 한 경우는 인덱스로 값을 잡았기 때문에 보완해주기 위해서 + 1을 한 결과값을 출력함

 

5. 문제를 푸는데 도움이 되는 지식

 

• 이분 탐색