[백준_11663번] 선분 위의 점

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

11663번: 선분 위의 점

[문제]

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.ㅋ

 

[코드]

import java.util.*;

public class BaekJoon_11663 {
	static int[] point;
	static int n,m;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		point=new int[n];
		for(int i=0;i<n;i++)
			point[i]=sc.nextInt();
		
		Arrays.sort(point); // 이진탐색을 위한 정렬
		
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<m;i++) {
			int s=sc.nextInt();
			int e=sc.nextInt();
			
			sb.append(binarySearch(s,e)).append('\n');
		}
		System.out.println(sb);
	}
	
	/*
	 * 이진탐색 
	 * 선분의 좌표를 (x,y)라고 할 때
	 * x를 기준으로 x를 포함한 오른쪽 부분의 인덱스
	 * y를 기준으로 y를 포함한 오른쪽 부분의 인덱
	 * y-x를 통해 점으로 주어진 좌표상에서 선분 사이에 있는 점의 개수를 구할 수 있다. 
	 */
	static int binarySearch(int x, int y) {
		int start=0;
		int end=point.length-1;
		
		// 선분의 y좌표보다 작은 점들의 개수 count
		while(start<=end) {
			int mid=(start+end)/2;
			
			if(point[mid]>y)
				end=mid-1;
			
			else 
				start=mid+1;
		}
		
		int endIndex=end+1;
		
		start=0;
		end=point.length-1;
		
		// 선분의 x좌표보다 작은 점들의 개수 count
		while(start<=end) {
			int mid=(start+end)/2;
			
			if(point[mid]<x)
				start=mid+1;
				
			else 
				end=mid-1;
		}
		
		int startIndex=start;
		
		return endIndex-startIndex;
	}

}

 

[고찰]

 이번 문제는 이진탐색으로 풀어야함은 파악했지만 어떻게 코드를 짜야하는지는 떠오르지 않아 다른 사람의 코드를 참고했다. 찾아보니 해결방법은 생각보다 간단해 이를 떠올리지 못한것이 아쉬웠다. 

 선분의 시작점과 끝점이 주어질 때 끝점보다 같거나 작은 점들의 개수에서 시작점보다 작은 개수를 빼주면 선분 안에있는 점의 개수가 된다. 이는 두 번의 이진탐색을 사용하면 구현할 수 있었고, 구현은 어렵지 않게 해결 가능했다.