[백준] Silver III. 선분 위의 점

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

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

3881

1413

1056

36.401%

문제

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

입력

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

출력

입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

3
2
4
2
0

 

 

사용 알고리즘

• 이분 탐색

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int [] arr;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        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);
        for(int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int lo = Integer.parseInt(st.nextToken());
            int hi = Integer.parseInt(st.nextToken());

            sb.append(upperbound(hi) - lowerbound(lo)).append("\n");
        }
        System.out.println(sb);
    }

    public static int lowerbound(int key) {
        int lo = 0;
        int hi = n;
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (key <= arr[mid]) {
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    public static int upperbound(int key) {
        int lo = 0;
        int hi = n;
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (key < arr[mid]) {
                hi = mid;
            }
            else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

 

회고

 

문제에서 두가지 좌표인 시작점과 끝점이 주어졌을 때, 그 사이에 주어진 점의 개수를 구하는 문제다.

 

이 문제를 공부하면서 처음에 감이 오지 않았는데, lowerbound와 upperbound 개념을 블로그에서 참고하고 공부하니 많은 도움이 됐다.

 

참고한 블로그)

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]

 

문제에서 

1 3 10 20 30

 

1, 10이 시작점과 끝점으로 주어질 때의 인덱스는 당연히 [1,3]이다.

 

그런데 20,60과 같이 해당 좌표에 정확히 위치하지 않을 때는 어떻게 계산할 것인가?

60이 끝 점으로 주어졌을 때는 key값인 30을 초과하는 인덱스를 가져야한다.  그렇기 때문에 key < arr[mid]처럼 초과하는 값을 찾고 인덱스를 계산해주면 된다.

 

반면에 lowerbound를 계산할 때는 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 계산해야 하므로, key <= arr[mid]와 같이 계산해주어야 한다.