[11663] 선분 위의 점

🔗 문제 링크

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

🔍 문제 설명

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

⚠️ 제한사항

• 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000)

• 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다.

• 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다.

• 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.

🗝 풀이 (언어 : Java)

이분 탐색을 통해 풀어야 한다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] points = new int[n];
        StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            points[i] = Integer.parseInt(st2.nextToken());
        }
        int[][] lines = new int[m][2];
        for (int i = 0; i < m; i++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine(), " ");
            lines[i][0] = Integer.parseInt(st3.nextToken());
            lines[i][1] = Integer.parseInt(st3.nextToken());
        }
        br.close();
        solution(points, lines);
    }

    private static void solution(int[] points, int[][] lines) {
        Arrays.sort(points);
        for (int[] line : lines) {
            System.out.println(getUpperBound(points, line[1]) - getLowerBound(points, line[0]));
        }
    }

    private static int getLowerBound(int[] points, int start) {
        int left = 0;
        int right = points.length - 1;
        while (left <= right) {
            int idx = (left + right) / 2;
            if (points[idx] < start) {
                left = idx + 1;
                continue;
            }
            right = idx - 1;
        }
        return right;
    }

    private static int getUpperBound(int[] points, int start) {
        int left = 0;
        int right = points.length - 1;
        while (left <= right) {
            int idx = (left + right) / 2;
            if (points[idx] > start) {
                right = idx - 1;
                continue;
            }
            left = idx + 1;
        }
        return right;
    }

}