[BOJ] 1633: 이분탐색

[BOJ 11663: 선분 위의 점] 문제 바로가기

❓문제 설명

첫째 줄의 N은 점의 개수, M은 선분의 개수이다.

두 번째 줄은 N개의 점 위치이고, 세 번째 줄부터 M개의 줄은 선분의 시작점과 끝점이 공백을 기준으로 입력된다.

각 선분에 몇 개의 점이 포함되어 있는지 출력하면 되는 문제.

ex) 선분 1-10 안에는 점 1, 3, 10이 존재하므로 3 출력

❗️문제 풀이

이분 탐색을 통해 주어진 선분 내에 들어올 수 있는 점을 찾았다.

이때 주의해야 할 점은 시작점과 끝점을 각각 다르게 구해야 한다는 것이다.

private static int binarySearch(long start, int check){  
				// check에 숫자를 담아 최저점을 찾는지, 최고점을 찾는지
        int left = 0;
        int right = dots.length - 1;

        if(check == 0){
            while(left <= right){
                int mid = (left+right)/2;
                if(dots[mid] < start){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            return left;
        }
        else{
            while(left <= right){
                int mid = (left+right)/2;
                if(dots[mid] > start){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            return right;

        }
    }

이때, binarySearch 함수에 check라는 인자를 통해 시작점을 구하는 것인지, 끝 점을 구하는 것인지 확인할 수 있도록 한다.

left는 시작점, Right는 끝점으로 두고 좁혀나가면 된다.

처음엔 코드가 같기 때문에 한 번에 처리하려고 했지만, 

시작점과 끝점을 나눠서 구해야 함을 알게 됐다.

📌전체코드

package 항해99;

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

public class jan_15th {
    static long[] dots;
    
    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());

        StringTokenizer st_N = new StringTokenizer(br.readLine());
        dots = new long[N];
        for(int i = 0; i < N; i++){
            dots[i] = Long.parseLong(st_N.nextToken());
        }
        Arrays.sort(dots);

        while(M > 0){
            // System.out.println(M);
            M--;
            StringTokenizer st_M = new StringTokenizer(br.readLine());
            long start = Long.parseLong(st_M.nextToken());
            long end = Long.parseLong(st_M.nextToken());

            int start_idx = binarySearch(start, 0);
            int end_idx = binarySearch(end, 1);
            
            System.out.println(end_idx + 1 - start_idx);

        }
    }
    private static int binarySearch(long start, int check){  // check에 숫자를 담아 최저점을 찾는지, 최고점을 찾는지
        int left = 0;
        int right = dots.length - 1;

        if(check == 0){
            while(left <= right){
                int mid = (left+right)/2;
                if(dots[mid] < start){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            return left;
        }
        else{
            while(left <= right){
                int mid = (left+right)/2;
                if(dots[mid] > start){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }
            return right;

        }
    }
}