[백준 11663]선분 위의 점(Java)

문제

www.acmicpc.net/problem/11663

풀이

이분탐색으로 푸는 문제이다.

1. 점들을 오름차순으로 정렬한다.

2. 선분에 포함되는 점들 중에서 최소값 좌표와 최대값 좌표를 이분탐색을 통해 각각 구한다.

3. 전체 점들의 개수에서, 최소값 좌표보다 작은 점과 최대값 좌표보다 큰 점의 개수를 뺀다.

코드

import java.io.*;
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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        int[] point = new int[N];
        for(int i=0;i<N;i++) point[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(point);
 
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int sum = M;
 
            int left = 0; int right = N-1;
 
            while(left<=right){
                int mid = (left+right)/2;
 
                if(point[mid]>=a) right = mid-1;
                else left = mid+1;
            }
            sum -= left;
            right = N-1;
            while(left<=right){
                int mid = (left+right)/2;
 
                if(point[mid]>b) right = mid-1;
                else left = mid+1;
            }
            sum -= (M-left);
            bw.write(sum+"\n");
        }
        br.close();
        bw.close();
    }
}