[99클럽 5기 코테 스터디 TIL 3일차] 선분 위의 점 (feat. 이진탐색)

1) 문제

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

문제

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

예제 입력 1 복사

5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8

예제 출력 1 복사

3
2
4
2
0

 

 

2) 문제 풀이

 

• 정렬
  • 점의 좌표를 먼저 정렬
  • 정렬된 상태에서 이진 탐색을 수행할 것
• 선분 처리:
  • 각 선분에 대해 시작점과 끝점을 기준으로 점의 범위를 이진 탐색으로 찾음
  • lower_bound: 시작점보다 크거나 같은 첫 번째 점의 위치.
  • upper_bound: 끝점보다 큰 첫 번째 점의 위치.
  • 두 인덱스의 차이를 구하면 해당 선분에 포함된 점의 개수를 알 수 있음.
• 효율성:
  • 점의 정렬: O(Nlog⁡N)O(N \log N)O(NlogN).
  • 각 선분에 대한 탐색: O(Mlog⁡N)O(M \log N)O(MlogN).
  • 총 시간 복잡도: O((N+M)log⁡N)O((N + M) \log N)O((N+M)logN).

 

 

 

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 입력 받기
        int n = sc.nextInt(); // 점의 개수
        int m = sc.nextInt(); // 선분의 개수
        int[] points = new int[n];
        for (int i = 0; i < n; i++) {
            points[i] = sc.nextInt();
        }

        // 점을 정렬
        Arrays.sort(points);

        // 선분 처리
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();

            // lower_bound와 upper_bound 계산
            int lower = lowerBound(points, start);
            int upper = upperBound(points, end);

            // 선분 내 점의 개수 계산
            result.append(upper - lower).append("\n");
        }

        // 결과 출력
        System.out.print(result);
    }

    // lower_bound 구현: target보다 크거나 같은 첫 위치
    private static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    // upper_bound 구현: target보다 큰 첫 위치
    private static int upperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}