[백준] 선분 위의 점 - 자바 Java

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

 

사용되는 개념: 이분탐색

선분의 시작점(a)부터 끝점(b) 사이 점의 개수는 'b보다 큰 점의 index' - 'a보다 크거나 같은 점의 index'로 구할 수 있다.

이는 다른 말로 upperbound, lowerbound의 개념으로 볼 수도 있다. 

 

Upper Bound, Lower Bound

• 이분탐색은 '원하는 값을 찾는 과정'이라면, Lower Bound는 '원하는 값이 처음 나오는 위치'를 찾는 과정이고 Upper Bound는 '원하는 값이 나오는 마지막 위치'를 찾는 과정이라고 볼 수 있다.
  • Upper Bound는 특정 값을 초과하는 첫 번째 위치를 반환한다.
  • Lower Bound는 특정 값 이상인 값인 첫번째 위치를 반환한다.
• 둘의 가장 큰 차이는 중복 값이 있을때다.
  • e.g. [1, 2, 3, 4, 5, 5, 6, 7] 와 같은 배열에서 5를 찾고자 할때 upperbound는 6(6의 index), lowerbound는 4(첫번째 5의 index)를 리턴한다. 
• 어쨌든 둘 다 이분탐색의 2가지 방식으로 생각한다.

다시 문제풀이로 돌아와서, 점의 개수 구할때 upperbound(b) - lowerbound(a)를 각각 함수로 구현해도 되고

아래와 같이 하나의 함수에서 이분탐색을 두 번 돌리는 식으로 간단하게 구현이 가능하다.

static int binarySearch(int x, int y) {
    // endIndex: y보다 큰 점의 index
    int left = 0;
    int right = dot.length - 1;
    
    while(left<=right) {
    	int mid = (left+right)/2;
        if(dot[mid] > y){
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    int endIndex = right + 1;
    
    // startIndex: x보다 크거나 같은 점의 index
    int left = 0;
    int right = dot.length - 1;
    
    while(left<=right) {
    	int mid = (left+right)/2;
        if(dot[mid] < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    int startIndex = left;
}

 

그리고 입력 받은 점의 개수는 꼭 정렬을 하고 이분탐색을 해야 한다는 점

전체코드

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

public class Main
{
    static int[] dot;
    
	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());
        
        dot = new int[N];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            dot[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(dot);
        
        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 result = binarySearch(a, b);
            System.out.println(result);
        }
	}
	
	static int binarySearch(int x, int y) {
        int left = 0;
        int right = dot.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (dot[mid] > y) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        int endIndex = right + 1;

        left = 0;
        right = dot.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (dot[mid] < x) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        int startIndex = left;

        return endIndex - startIndex;
    }
}