문제 탐색하기

입력 자료 정리

1. 입력값 n은 좌표상에 주어지는 점의 개수다
2. 입력값 m은 찾고자 하는 범위의 개수로 사실상 테스트케이스다
3. 이후 들어오는 n개의 입력값은 좌표상에 있는 점의 위치다
4. 이어서 m만큼 들어오는 두 수는 범위의 시작과 끝이다

해결방법 추론

1. 좌표의 최대값이 1억이기 때문에 이분탐색을 선택하여 풀어야겠다고 생각했다
2. 이분탐색을 위해서는 먼저 주어지는 원소값들을 오름차순 정렬해야한다
3. 이 문제에서는 인덱스를 기준으로 이분탐색을 해야한다
4. 또한 시작지점의 최적의 위치와 끝 지점의 최적의 위치를 각각 이분탐색해야한다

이분탐색 방법 고민

1. 이분탐색을 어떻게 할 수 있을까?
   나눠서 두개의 메소드를 만드는 방법도 있지만
   하나의 이분탐색에서 타입을 구분해서 나눠서 탐색하도록 설계하면 더 편리하게 할 수 있다
2. 범위의 시작지점은 left를 줄여서 최적의 시작 위치를 찾고
   범위의 끝 지점은 right를 줄여서 최적의 끝 위치를 찾는다
3. 시작지점은 중간 지점의 원소값보다 시작 지점이 큰 경우 left를 늘리는 방향으로,
   끝지점은 중간지점의 원소값보다 끝 지점이 작은 경우 right를 줄이는 방향으로 하면 될 것이다

시간복잡도 계산

1. 이분탐색에서 시간복잡도는 logn이 발생한다.
2. 이것을 m만큼 순회하면서 진행하므로 시간복잡도는 O(m x logn)이 된다
3. 따라서 시간 제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. n과 m은 변수로 관리한다
2. n만큼 들어오는 입력값들은 int형 1차원 배열에 관리한다
3. m만큼 순회하면서 들어오는 두 값은 a와 b 변수에 관리한다

이분탐색 설계

1. 이분탐색은 left는 0, right는 n-1로 초기화하여 인덱스의 범위로 잡는다
2. type이 1일때는 시작지점에 대해서, 2일 때는 끝지점에 대해서이다
3. 시작지점일 때와 끝 지점일 때 각각 이분탐색을 진행하며, left와 right+1을 리턴한다
4. right일 경우는 +1을 해줘야하는데,
   인덱스가 0번부터 시작하기 때문에 개수가 한개 누락될 수 있기 때문이다
5. 이분탐색의 반환타입으로 int형 타입을 지정하여 변수로 받아 관리한다

출력값 설계

1. 이분탐색결과 시작지점과 끝지점 변수를 서로 빼준다
2. 이때 끝지점 변수에서 시작지점 변수를 빼준 값을 출력하면 정답이 되는데,
   두 지점의 차이가 인덱스 차이이므로, 선분 위에 주어진 점의 개수이기 때문이다.

정답코드

(1회차 시도 성공!)

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


public class Main {

    static int[] arr;
    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());
        int n = Integer.parseInt(st.nextToken());
        int 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 a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int ansStart= indexBinarySearch(a, 1, n);
            int ansEnd = indexBinarySearch(b, 2, n);
            bw.write((ansEnd - ansStart) + "\n");
        }

        br.close();
        bw.close();
    }

    private static int indexBinarySearch(int now, int type, int n) {
        int left = 0;
        int right = n-1;
        if(type == 1){
            while(left <= right){
                int mid = (left + right) / 2;
                if(arr[mid] < now){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }

            return left;
        }
        while(left <= right){
            int mid = (left + right) / 2;
            if(arr[mid] > now){
                right = mid - 1;
            }else{
                left = mid+1;
            }
        }
        return right+1;
    }

}

문제 링크

11663 - 선분 위의 점