백준 선분 위의 점

문제

내가 생각했을때 문제에서 원하는부분

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

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

내가 이 문제를 보고 생각해본 부분

입력 처리: BufferedReader를 사용하여 입력을 받는다.
정렬: 입력받은 점의 좌표를 정렬해준다.
이분 탐색: 각 선분에 대해 시작점과 끝점 범위 내에 있는 점의 개수를 계산하기 위해 lowerBound와 upperBound 메소드를 구현하여 이분 탐색을 해준다.
결과 출력: 각 선분에 포함된 점의 개수를 출력한다.

코드로 구현

package baekjoon.baekjoon_26;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

// 백준 11663번 문제
public class Main929 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 점의 개수 N과 선분의 개수 M을 입력받는다.
        String[] firstLine = br.readLine().split(" ");
        int N = Integer.parseInt(firstLine[0]);
        int M = Integer.parseInt(firstLine[1]);

        // 점의 좌표를 입력받는다.
        int[] points = new int[N];
        String[] pointsInput = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            points[i] = Integer.parseInt(pointsInput[i]);
        }

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

        // 선분의 시작점과 끝점을 입력받고 결과를 저장한다.
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < M; i++) {
            String[] segment = br.readLine().split(" ");
            int start = Integer.parseInt(segment[0]);
            int end = Integer.parseInt(segment[1]);

            // 이분 탐색을 통해 선분 내에 있는 점의 개수를 계산한다.
            int count = countPointsInSegment(points, start, end);
            result.append(count).append("\n");
        }

        // 결과를 출력한다.
        System.out.print(result);
        br.close();
    }

    // 선분 [start, end] 내에 있는 점의 개수를 반환하는 메소드
    static int countPointsInSegment(int[] points, int start, int end) {
        int leftIndex = lowerBound(points, start);
        int rightIndex = upperBound(points, end);
        return rightIndex - leftIndex;
    }

    // 주어진 값보다 크거나 같은 첫 번째 인덱스를 찾는 이분 탐색
    static int lowerBound(int[] points, int value) {
        int low = 0, high = points.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (points[mid] < value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    // 주어진 값보다 큰 첫 번째 인덱스를 찾는 이분 탐색
    static int upperBound(int[] points, int value) {
        int low = 0, high = points.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (points[mid] <= value) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.