코딩 챌린지 14일차 : 11663번 선분 위의 점(S3)

11663 : 선분 위의 점 - 문제 링크

1. 문제 탐색하기

입력

n 점의 개수
m 선분의 개수
dots[n] 점의 좌표
start, end 선분의 시작점과 끝점

구하고자 하는 것

각 선분 위에 있는 점의 개수

알고리즘 설계

각 선분마다 모든 점에 대해 계산하면 m * n번의 연산을 하므로
최대 10 ^ 10번의 연산 수행 -> 시간 초과 발생
이를 피하기 위해서는 이분탐색을 사용해야 한다.

우선, 점 리스트를 정렬한 후
선분 위의 가장 왼쪽, 오른쪽 점 각각을 이분탐색으로 찾는다.
두 점 사이의 점들은 선분 위에 있게 되므로
두 점을 포함한 사이 점들의 개수를 구한다. (index 사용)

시간복잡도

점들에 대해 이분 탐색 -> log n
모든 선분에 대해 탐색 -> m
=> m log n의 시간복잡도를 가짐
1 $\leq$ n, m $\leq$ 100,000 이므로 시간 내에 통과 가능

2. 코드 설계하기

1. input 받기, 초기 변수 설정
2. 점 리스트 정렬하기
3. 선분 정보 input 받을 때마다 아래의 계산 수행
1. 이분탐색으로 선분 위의 가장 왼쪽 점 구하기
2. 이분탐색으로 선분 위의 가장 오른쪽 점 구하기
3. 두 점의 index 뺄셈으로 사이의 점 개수 구하고 출력

3. 시도 회차 수정 사항

1회차) 정렬된 자료만 들어오나? 긴가민가해서 sort를 하지 않음
2회차) dots.sort() 작성 후 정답!

정렬된 자료가 주어질 때는 지문에 명시됨. sort는 최적화된 정렬 함수이므로 이용하자!

4. 정답 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
dots = list(map(int, input().split()))
dots.sort()

def binary_search(lr, target):
    start, end = 0, len(dots) - 1

    while start <= end:
        cur = (start + end) // 2
        if dots[cur] < target:      start = cur + 1
        elif dots[cur] > target:    end = cur - 1
        else:                       return cur

    # L, R에 따라 선분 내의 점을 반환하기 위한 처리
    if lr == 0:     return start
    elif lr == 1:   return end

# 매 선분 정보마다 계산
for _ in range(m):
    start, end = map(int, input().split())

    left = binary_search(0, start)
    right = binary_search(1, end)

    print(right - left + 1)

이 챌린지로 시간복잡도를 계산해보는 연습을 하지 않았더라면 실컷 브루트포스로 짠 후 시간 초과를 먹었을 것 같다. 설계와 템플릿 작성의 중요성을 체감하는 문제였다 ~

5. 해설지 참고 후

• bisect 라이브러리를 사용하는 방법도 있음

import bisect
import sys
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(bisect.bisect_right(arr, b) - bisect.bisect_left(arr,a))