[BOJ] 11663. 선분 위의 점 (java)

✏️ 문제

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

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

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

 

🔢 알고리즘

 

#이진탐색

 

 

🤯 풀이 방법

무작정 반복문으로 탐색을 돌렸더니 시간초과가 났다.

이진 탐색으로 시작 위치와 끝 위치 인덱스를 찾아서 그 사이 거리를 구해야 했다.

답이 정확하게 떨어지지 않으니 같을 때나 크거나 작을 때의 처리하는 게 너무 헷갈린다 🥲

 

 

👾 구현 코드 (자바)

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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()); // 선분의 개수

        long[] points = new long[N];    // 점 좌표 입력
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            points[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(points);    // 점 좌표 순서대로 정렬

        StringBuilder sb = new StringBuilder();

        for (int j = 0; j < M; j++) {   // 선분 하나씩 탐색
            st = new StringTokenizer(br.readLine());
            long from = Long.parseLong(st.nextToken());  // 선분 시작점 입력
            long to = Long.parseLong(st.nextToken());      // 선분 끝점 입력

            // 시작보다 작은 위치 찾기
            long start = 0;
            long end = N - 1;
            long mid1 = 0;
            long mid2 = N - 1;

            while (start <= end) {
                mid1 = (start + end) / 2;
                if (points[(int) mid1] < from) {
                    start = mid1 + 1;
                } else {
                    end = mid1 - 1;
                }
            }
            long startIdx = start;

            // 끝점보다 작은 점 수 찾기
            start = 0;
            end = N - 1;
            while (start <= end) {
                mid2 = (start + end) / 2;
                if (points[(int) mid2] > to) {
                    end = mid2 - 1;
                } else {
                    start = mid2 + 1;
                }
            }
            long endIdx = end + 1;
            sb.append(endIdx - startIdx);
            if (j != M - 1) {
                sb.append("\n");
            }
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}