[Python/Java] 백준 11663 - 선분 위의 점 [이진 탐색]

문제

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

 

해설

이 문제도 이진 탐색을 이용하여 해결하여야 시간초과가 발생하지 않는 문제였다.

 

Python

from sys import stdin


def min_bin_search(N, point, lst):
    start = 0
    end = N - 1

    while start <= end:
        mid = (start + end) // 2

        if lst[mid] < point:
            start = mid + 1
        else:
            end = mid - 1

    return end


def max_bin_search(N, point, lst):
    start = 0
    end = N - 1

    while start <= end:
        mid = (start + end) // 2

        if point < lst[mid]:
            end = mid - 1
        else:
            start = mid + 1

    return end


def solution(N, M, lst):
    lst = sorted(lst)

    for _ in range(M):
        line = list(map(int, stdin.readline().split(" ")))
        print(max_bin_search(N, line[1], lst)-min_bin_search(N, line[0], lst))


n, m = map(int, stdin.readline().split(" "))
points = list(map(int, stdin.readline().split(" ")))
solution(n, m, points)

 

Java

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

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

        String[] condition = br.readLine().split(" ");
        long n = Long.parseLong(condition[0]);
        long m = Long.parseLong(condition[1]);
        
        String[] pointsInput = br.readLine().split(" ");
        List<Long> points = new ArrayList<>();
        for (String v : pointsInput) {
            points.add(Long.parseLong(v));
        }
        Collections.sort(points); 

        for(int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            long left = Long.parseLong(line[0]);
            long right = Long.parseLong(line[1]);

            long startIdx = minBinSearch(left, points);
            long endIdx = maxBinSearch(right, points);
            sb.append(endIdx - startIdx).append("\n");
        }

        System.out.print(sb.toString());
    }

    public static long minBinSearch(long point, List<Long> lst) {
        long start = 0;
        long end = lst.size() - 1;

        while(start <= end) {
            long mid = (start + end) / 2;

            if(lst.get((int) mid) < point) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return end;
    }

    public static long maxBinSearch(long point, List<Long> lst) {
        long start = 0;
        long end = lst.size() - 1;

        while(start <= end) {
            long mid = (start + end) / 2;

            if(point < lst.get((int) mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return end;
    }
}