[Python] 11663 - 선분 위의 점

 

1. 문제 정의

점의 개수와 선분의 개수가 주어지고, 일차원상의 점의 좌표와 선분이 주어진다. 각 선분마다 해당 점이 몇 개 존재하는지를 구하는 프로그램을 작성하는 문제이다.

 

2. 풀이 방식

오름차순으로 정렬된 점 리스트에서 선분에 존재하는 점의 처음과 끝을 알아낸다면, 전체 개수를 알 수 있다.

처음의 점과 끝의 점을 구하기 위해 이분 탐색을 이용하여 점을 구하고 (이때의 값은 점의 인덱스 번호로 정의할 수 있다.) 두 결과값의 차를 이용해 점의 개수를 알 수 있다.

# 11663 선분 위의 점

N, M = map(int, input().split())

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

def dot_min(a):  # 선분 중 가장 작은 점 구하기 
    start = 0
    end = N - 1

    while (start <= end):
        mid = (start + end) // 2

        if (a > point[mid]):
            start = mid + 1
        else:
            end = mid - 1

    return end

def dot_max(b):   # 선분 중 가장 큰 점 구하기
    start = 0
    end = N - 1

    while (start <= end):
        mid = (start + end) // 2

        if (b < point[mid]):
            end = mid - 1
        else:
            start = mid + 1

    return end

for _ in range(M):
    a, b = map(int, input().split())
    print(dot_max(b) - dot_min(a))

 

3. 후기

정답을 알고나니 단순한 로직이라 생각이 들지만, 처음에 알고리즘 설계 단계에서는 이를 생각해내기 쉽지 않았다.

알고리즘 분류에도 나와있듯이 입력받은 점의 리스트를 정렬하는 것이 이 문제의 핵심이라 생각한다.