[백준-실버] 선분 위의 점(BOJ 11663)

문제

선분 위의 점 

 

풀이

N과 M의 최대 개수는 100,000이고 시간 제한은 1초이기에 n^2 은 시간초과가 발생합니다. 무조건 M번은 반복문을 돌려야 하고 실행당 포함하는 점의 개수를 구하기 위해 longN의 시간복잡도를 갖는 탐색 알고리즘이 필요합니다. 그래서 이분 탐색을 이용해 해당 문제를 풀었습니다.

 

선분위의 점의 개수는 선분이 포함한 점의 `최대값의 인덱스 - 최소값의 인덱스 + 1` 을 통해 구할 수 있습니다.선분의 최소값의 인덱스는 선분의 왼쪽값과 `같거나 큰(큰 값들 중 최소)값`의 점 인덱스를 의미하고 최대값의 인덱스는 선분의 오른쪽값과 `같거나 작은(작은 값들 중 최대)값`의 점 인덱스를 의미하고, 해당 인덱스들은 이분탐색을 통해 구할 수 있습니다.

 

수도 코드

• 정수타입 N, M을 입력받는다.
• 정수형 배열 arr에 점 N개를 입력받는다.
• arr를 오름차순으로 정렬한다.
• for(M 개만큼 반복) 
• {
• 선분 을 입력받는다.
• 최소 인덱스, 최대 인덱스를 구한다.
• StringBuilder에 최대 인덱스 - 최소 인덱스 + 1을 저장한다.
• }
• StringBuilder를 출력한다.

 

코드

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

public class 선분_위의_점 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] 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);

        int left = 0;
        int right = 0;

        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            left = Integer.parseInt(st.nextToken());
            right = Integer.parseInt(st.nextToken());

            int leftValue = leftBinarySearch(arr, left);
            int rightValue = rightBinarySearch(arr, right);

            sb.append(rightValue - leftValue + 1).append("\n");

        }

        System.out.println(sb);
    }

    public static int leftBinarySearch(int[] arr, int left) {
        int start = 0;
        int end = arr.length - 1;
        int result = arr.length;
        while(start <= end) {
            int mid = (start + end)/ 2;
            if(arr[mid] >= left){
                result = mid;
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }
        return result;
    }

    public static int rightBinarySearch(int[] arr, int right) {
        int start = 0;
        int end = arr.length-1;
        int result = -1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(arr[mid] <= right) {
                result = mid;
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return result;
    }
}

 

회고

처음에는 이분 탐색시 start, end의 값을 인덱스가 아닌 arr에 인덱스를 적용한 값으로 문제를 풀었었고, 시간 초과가 발생했었다. 조금만 더 고민했었으면 인덱스 비교를 할 수 있었을텐데 좀 아쉬운 풀이었다.