[백준/Java] 11663번 : 선분 위의 점

✏️ 문제 분석

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

 

일차원 좌표 상에 점 N개, 선분 M개가 있을 때

각각의 선분에 점이 몇 개 있는지 구하는 문제이다.

✏️ 구현 아이디어

브루트 포스는 시간 초과

브루트 포스를 사용하면

각 M개의 선분 마다 점이 몇 개 있는지 찾아야 하고

점의 개수는 1~N이 될 수 있다.

그래서 시간 복잡도가 O(M*N)

 

만약 점이 10억개가 있고 선분이 1부터 10억까지의 길이라면

선분이 한 개만 있어도 10억번의 연산이 필요하다.

 

이분 탐색으로 풀어보자

5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8

처음에는 이분탐색 대상을 뭘로 해야 좋을지 떠오르지 않았다.

이전 문제처럼 구해야 할 대상인 '선분 위 점의 개수'로 두고 풀려니 어려웠다.

 

1. 우리는 지금 점의 위치와 개수를 알고 있으므로 

뺄셈을 통해 점 a와 b 사이에 몇 개의 점이 있는지 구할 수 있다.

 

 

2. 선분 시작점과 끝점을 알고 있으므로

선분의 시작점 앞에 있는 점 중 가장 끝 점, 선분의 끝점 뒤에 있는 점 중 가장 앞의 점

두 가지를 구할 수 있다.

 

예)

만약 선분 2~15라면 점1, 점20이 이에 해당한다.

점 1과 20 사이에는 2개의 점이 있으므로, 선분 2~15위의 점은 총 2개이다.

 

👉🏻 여기서 이분탐색을 어디에 적용할 수 있냐면..

1. 선분의 시작점 2 앞에 있는 점 중 가장 끝 점을 찾을 때

2. 선분의 끝점 15 뒤에 있는 점 중 가장 앞에 있는 점을 찾을 때

 

이 아이디어로 풀어도 좋은데,

이분탐색에는 upper bound, lower bound라는 개념이 있다.

이 개념을 활용하면 더 쉽게 풀 수 있다!

🖍️🖍️ Upper Bound, Lower Bound를 활용한 풀이 🖍️🖍️

이분탐색과 관련하여 자주 등장하는 개념으로 Upper Bound, Lower Bound가 있다.

이 개념은 주로 정렬된 리스트에서 어떤 숫자의 삽입 위치를 찾기 위해 사용된다.

 

📍Lower Bound

배열에서 어떠한 값(k)보다 크거나 같은 값이 처음 나오는 위치를 구하는 방법

📍Upper Bound

배열에서 어떠한 값(k)보다 큰 값이 처음 나오는 위치를 구하는 방법

 

이 문제의 경우,

선분의 시작점(a)의 Lower Bound에서

선분의 끝점(b)의 Upper Bound를 빼면

선분 ab 위에 있는 점의 개수를 구할 수 있다!

 

예)

 

점이 1, 3, 10, 20, 30에 있다면

시작점이 3, 끝점이 22인 선분 위에는 3개의 점이 존재한다.

끝점의 upper bound - 시작점의 lower bound

= 4-1

= 3

= 구하려는 점의 개수

 

따라서 선분 시작 점의 lower bound, 끝점의 upper bound 두 가지를 이분 탐색으로 구하자.

✏️ 알고리즘

이분 탐색 알고리즘

✏️ 시간 복잡도

좌표 개수는 최대 10억, 10억=10^9이므로 log10^9=9

따라서 시간 안에 연산 가능하다.

✏️ 코드 설계

1. 입력 받기
2. 이분탐색을 위해 점들을 오름차순 정렬
3. 선분의 start, end 위치를 입력받으면 start의 lower bound, end의 upper bound를 찾기
4. 둘의 차이를 출력

lower bound, upper bound를 구하는 방법은 while문의 조건에 등호가 있는지, target보다 mid가 큰지 확인하는 조건에 등호가 있는지 등 내가 설계한 것에 따라 달라지므로 직접 작은 예제를 시행해보고 start, end 중에 적절한 것을 리턴하도록 만들자.. 항상 헷갈리는 부분 중 하나다ㅠ

✏️ 정답 코드

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

public class Main {
    static int N, M;
    static int[] points;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //입력 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        points = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            points[i] = Integer.parseInt(st.nextToken());
        }

        //점들을 오름차순으로 정렬
        Arrays.sort(points);

        for(int i=0; i<M; i++){
            //선분의 시작점, 끝점 입력받기
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            bw.write(upperBound(end)-lowerBound(start) + "\n");
        }
        bw.close();
    }

    static int lowerBound(int target){
        //타겟보다 크거나 같은 값이 처음 등장한 위치 탐색
        int start = 0;
        int end = N-1;

        while(start<=end){
            int mid = (start+end)/2;
            if(points[mid]>=target){
                //타겟을 찾았거나 타겟이 왼쪽에 있는 경우, 왼쪽 탐색
                end = mid-1;
            }else{
                //타겟이 오른쪽에 있는 경우, 오른쪽 탐색
                start = mid+1;
            }
        }
        return start;
    }

    static int upperBound(int target){
    	//타겟보다 큰 값이 가장 처음 등장한 위치 탐색
        int start = 0;
        int end = N-1;

        while(start<=end){
            int mid = (start+end)/2;
            if(points[mid]<=target){
                //타겟을 찾았거나 타겟이 오른쪽에 있는 경우, 오른쪽을 탐색
                start = mid+1;
            }else{
                //타겟이 왼쪽에 있는 경우
                end = mid-1;
            }
        }
        return start;
    }
}