문제 풀이

이분 탐색을 통해 선분의 시작지점 전으로는 몇개의 점이 있는지, 선분의 끝지점 이전으로는 몇개의 점이 있는지 확인하고 둘을 빼주면 선분의 시작과 끝을 포함한 부분에 몇개의 점이 있는지 구할 수 있다.

문제 링크

boj/11663

소스코드

PS/11663.java

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


    public class Main {
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        public static void main(String[] args) throws IOException {
            int n,m;
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int [] arr = new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arr);
            for(int i=0;i<m;i++)
            {
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                int l = 0, r= n- 1;
                while(l<=r)
                {
                    int mid = (l+r)/2;
                    if(arr[mid] >= s)
                        r= mid-1;
                    else
                        l = mid+1;
                }
                int a= l;
                l = 0; r= n- 1;
                while(l<=r)
                {
                    int mid = (l+r)/2;
                    if(arr[mid] > e)
                        r= mid-1;
                    else
                        l = mid+1;
                }
                int b= l;
              bw.write(Integer.toString(b-a)+"\n");

            }
            bw.flush();
        }

    }