[알고리즘 TIL] 11663. 선분 위의 점

문제

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

설명

이 문제를 푸는 알고리즘은 이진 탐색이다. 완전 탐색의 시간 복잡도는 N*M으로, 1초가 훨씬 넘어간다. 따라서 각 선분마다 점의 개수를 구하는 방식을 이진 탐색으로 풀어내면 O(M*LogN)으로 풀 수 있다.

 

선분 시작점과 종료점이 숫자들의 인덱스에 어디에 위치하는지 알아내면, (종료점 인덱스 - 시작점 인덱스) 가 점의 개수라는 것을 알 수 있다.

 

하지만 알고리즘을 구하고도, 조건문에서 많이 고려할 사항이 있다.

• 시작점이 모든 숫자보다 큰 경우
  • 점의 개수는 0개이다.
• 종료점이 모든 숫자보다 큰 경우
  • 종료점의 인덱스는 숫자들 중 제일 큰 수의 인덱스로 여긴다.
• 시작점 또는 종료점이 숫자 내에 존재할 경우
  • 해당 숫자의 인덱스이다.
• 시작점이 제일 큰 숫자보다는 같거나 작지만 없는 경우
  • (start + 1의 인덱스)의 숫자와 동일하게 여긴다.
• 종료점이 제일 큰 숫자보다는 같거나 작지만 없는 경우
  • (start - 1의 인덱스)의 숫자와 동일하게 여긴다.

구현

N,M = map(int,input().split(" "))
nums = list(map(int,input().split(" ")))
nums.sort()

def binary_search(nums,target,isStart):
    flag = 0
    def bs(start,end,target,flag):
        if start>end : 
            if flag == 0:
            	# 선분의 시작점을 주어진 숫자 내에서 못찾은 경우
                if isStart: return start   
                # 선분의 종료점을 주어진 숫자 내에서 못찾은 경우
                else: return start - 1
            return
        mid = (start + end) // 2
        if nums[mid] == target : 
            flag = 1
            return mid
        if nums[mid] > target : return bs(start,mid-1,target,flag)
        if nums[mid] < target : return bs(mid+1,end,target,flag)
    return bs(0,len(nums)-1,target,flag)

for _ in range(M):
    start, end = map(int,input().split(" "))
	
    # 선분의 시작점이 모든 숫자보다 큰 경우
    if start > nums[-1] : 
        print(0) 
        continue
    start_index = binary_search(nums,start,True)
    
    # 선분의 종료점이 모든 숫자보다 큰 경우
    if end > nums[-1] : 
        print(len(nums) -1 - start_index +1)
        continue
    end_index = binary_search(nums,end,False)
    
    print(end_index - start_index + 1)