[Algorithm] 99클럽 코테 스터디 3일차 TIL | 백준_선분 위의 점(11663번)

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

분명 이진 탐색 알고리즘인건 알겠는데..

그래서 어떻게 풀지 고민이 됐던 문제다.

 

우선 점의 좌표 배열을 오름차순으로 정렬하고

배열에서 선분의 시작점 이상인 첫번째 위치를 찾고

배열에서 선분의 끝점 이하인 첫번째 위치를 찾는다.

 

 그리고 이 위치를 찾기 위해 이분탐색을 활용한다.

import java.util.*;
import java.io.*;
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[] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken()); //시작점
            int b = Integer.parseInt(st.nextToken()); //끝점

            // 배열에서 a이상인 첫 번째 위치 반환
            int startIdx = lowerBound(arr, a);
            // 배열에서 b이하인 첫 번째 위치 반환
            int endIdx = upperBound(arr, b);
            sb.append(endIdx - startIdx).append("\n");
        }
        System.out.println(sb.toString());
    }
    public static int lowerBound(int[] arr, int a){
        int low = 0;
        int high = arr.length-1;

        while(low <= high){
            int mid = (low + high) / 2;
            if(arr[mid] >= a){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return low;
    }

    public static int upperBound(int[] arr, int b){
        int low = 0;
        int high = arr.length-1;

        while(low <= high){
            int mid = (low + high) / 2;
            if(arr[mid] <= b){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return high+1;
    }
}