230818 - [Java-Python] 이분탐색

[robert-min]

boj 1300, 1637

[robert-min]

BOJ.7795 먹을 것인가 먹힐 것인가 링크

파이썬 풀이

• binary 함수 호출 부분: 이진 탐색 함수인 binary을 a 리스트의 모든 요소마다 호출합니다. 이진 탐색의 시간 복잡도는 O(log m)입니다. 여기서 m은 b 리스트의 길이입니다. 이 부분이 n번 반복되므로 총 시간 복잡도는 O(n log m)입니다.
• solution 함수 내에서의 반복문: solution 함수는 a 리스트의 모든 요소마다 binary 함수를 호출하며, 이 부분이 n번 반복됩니다. 각 binary 함수의 시간 복잡도는 O(log m)이므로, 이 부분의 총 시간 복잡도도 O(n log m)입니다.
• 전체적인 시간 복잡도는 O(n log m + n log m) = O(n log m)입니다.

import sys
input = sys.stdin.readline

def binary(b, start, end, target):
    res = start-1
    while start <= end:
        mid = (end + start) // 2
        if b[mid] < target:
            res = mid
            start = mid + 1
        else: 
            end = mid - 1
    return res

def solution():
    b.sort()
    ans = 0
    for i in a:
        ans += binary(b, 0, m-1, i) + 1
    print(ans)

T = int(input())
for _ in range(T):
    n, m = map(int ,input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    solution()

• bisect_right (시간초과)
• 시간복잡도 :
  • 정렬할 때 NlogN
  • a의 각 요소마다 이진 탐색을 통해 b에서 해당 요소보다 큰 수의 개수를 찾는데 걸리는 시간은 O(log M) * N 번 반복
  • (NlogN + NlogM)

java 풀이

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int[] A, B;

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        A = new int[N+1];
        B = new int[M+1];
        for (int i = 1; i <= N; i++) {
            A[i] = scan.nextInt();
        }
        for (int i = 1; i <= M; i++) {
            B[i] = scan.nextInt();
        }
    }
    static int search(int[] B, int L, int R, int X) {
        int result = L -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (B[mid] < X) {
                result = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
        return result;
    }

    static void solution() {
        // B sort
        Arrays.sort(B, 1, M + 1);

        int ans = 0;
        for (int i=1; i <=N; i++) {
            ans += search(B, 1, M, A[i]);
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        int TT;
        TT = scan.nextInt();
        for (int tt = 1; tt <= TT; tt++) {
            // input
            input();

            // search
            solution();

            // print
        }
    }
}

[robert-min]

2470 두용액 링크

python

n = int(input())
arr = sorted(map(int, input().split()))  # 정렬된 용액들

def binary_search(s, target):
    global arr
    res = n
    start, end = s, n - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= target:
            res = mid
            end = mid - 1
        else:
            start = mid + 1
    return res

def solution():
    global arr
    v1, v2 = 0, 0
    best_sum = 10 ** 10
    for i in range(n):
        # 이분 탐색 수행: 현재 위치(i) 이후의 용액에서 탐색, 찾는 값은 (현재 용액 * -1)
        res = binary_search(i + 1, -arr[i])

        # 찾은 용액의 왼쪽 용액 확인
        if i + 1 <= res - 1 < n and abs(arr[i] + arr[res - 1]) < best_sum:
            best_sum = abs(arr[i] + arr[res - 1])
            v1, v2 = arr[i], arr[res - 1]

        # 찾은 용액 확인
        if i + 1 <= res < n and abs(arr[i] + arr[res]) < best_sum:
            best_sum = abs(arr[i] + arr[res])
            v1, v2 = arr[i], arr[res]

    print(v1, v2) # i 번째 용액을 확인할 때 i + 1번 용액부터 확인하기 때문에 항상 v1 <= v2 이다.

solution()

java

import java.io.*;
import java.util.*;
public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N;
    static int[] A;
    static void input() {
        N = scan.nextInt();

        A = new int[N+1];
        for (int i = 1; i <= N; i++) {
            A[i] = scan.nextInt();
        }
    }

    static int search(int[] A, int L, int R, int X){
        int result = R + 1;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (A[mid] >= X) {
                result = mid;
                R = mid -1;
            } else {
                L = mid + 1;
            }
        }
        return result;
    }

    static void solution() {
        // sorted
        Arrays.sort(A, 1, N+1);

        int best_sum = Integer.MAX_VALUE;
        int v1 = 0, v2 = 0;
        // 왼쪽 용액 선택후 왼쪽 용액 기준으로 오른쪽 용액에서 -A[left]와 가장 가까운 용액 찾기
        for (int left = 1; left <= N - 1; left++) {
            // search
            int result = search(A, left + 1, N, -A[left]);

            // A[result -1] 와 A[result] 중 A[left]와 합했을 때 정답을 갱신
            if (left < result - 1 && Math.abs(A[left] + A[result-1]) < best_sum) {
                best_sum =  Math.abs(A[left] + A[result-1]);
                v1 = A[left];
                v2 = A[result-1];
            }
            if (result <= N && Math.abs(A[left] + A[result]) < best_sum) {
                best_sum =  Math.abs(A[left] + A[result]);
                v1 = A[left];
                v2 = A[result];
            }
        }
        sb.append(v1).append(" ").append(v2);
        System.out.println(sb);

    }

    public static void main(String[] args) {
        // input
        input();

        // solution
        solution();
    }
}

[robert-min]

BOJ2805. 나무자르기 링크

• 문제 풀이
  • 나무의 최대높이(10^6)에서 최소높이(0)까지 중 어떤 높이가 나무를 최소한으로 자르면서 m 값을 초과하는 지 찾는 문제
  • 이분탐색을 통해 해당 값 조회

    python 풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
trees = list(map(int, input().split()))

def determination(H):
    sum = 0
    for t in trees:
        if t > H:
            sum += t - H
    return sum >= m

def binary_search(left, right):
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if determination(mid):
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
    return ans

print(binary_search(0, 1000000000))

java 풀이

import org.example.fastreader.FastReader;

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    static int[] trees;

    static void input() {
        N = scan.nextInt();
        M = scan.nextInt();
        trees = new int[N + 1];

        for (int i=1; i <= N; i++) {
            trees[i] = scan.nextInt();
        }
    }

    static boolean determination(int H) {
        long sum = 0;
        for (int i = 0; i <= N; i++) {
            if (trees[i] > H) {
                sum += trees[i] - H;
            }
        }
        return sum >= M;
    }

    static void solution(){
        long L = 0, R = 2000000000, ans = 0;
        while (L <= R) {
            int mid = (int)((L + R) / 2);
            if (determination(mid)) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid -1;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        // input
        input();
        // solution
        solution();
    }

}

[robert-min]

BOJ.2110 공유기

• 문제 풀이
  • 두 공유기 사이 걸이를 최대로 할 수 있는 길이
  • 즉, 우리가 구하려는 것은 길이이고 두 공유기 사이의 길이는 최대 길이(100000000), 최소길이(1) 사이에서 찾아야함
  • 해당 값을 효과적으로 찾기위해 이분탐색을 하며 탐색 조건을 determination 함수를 통해 검증

python 풀이

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
X = list()
for _ in range(N):
    X.append(int(input()))

X.sort()
left, right, ans = 0, 100000000, 0

def determination(D):
    last = X[0]
    cnt = 1
    for i in range(N):
        if X[i] - last < D: continue

        last = X[i]
        cnt += 1
    return cnt >= C

while left <= right:
    mid = (left+ right) // 2
    if determination(mid):
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

print(ans)

java 풀이

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

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, C;
    static int[] A;

    static void input() {
        N = scan.nextInt();
        C = scan.nextInt();
        A = new int[N+1];
        for (int i = 1; i <= N; i++) {
            A[i] = scan.nextInt();
        }
    }

    static boolean determination(int D) {
        int cnt = 1, last = A[1];
        for (int i = 2; i <= N; i++) {
            if (A[i] - last < D) continue;
            cnt++;
            last = A[i];
        }
        return cnt >= C;
    }

    static void solution() {
        // sort
        Arrays.sort(A, 1, N+1);

        // Distance
        int L = 1, R = 1000000000, ans = 0;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (determination(mid)) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid -1;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        // input
        input();
        // solution
        solution();
    }

}

[robert-min]

입국심사 링크

def solution(n, times):
    answer = 0
    # right는 가장 비효율적으로 심사했을 때 걸리는 시간
    # 가장 긴 심사시간이 소요되는 심사관에게 n 명 모두 심사받는 경우이다.
    left, right = 1, max(times) * n
    while left <= right:
        mid = (left+ right) // 2
        people = 0
        for time in times:
            # people 은 모든 심사관들이 mid분 동안 심사한 사람의 수
            people += mid // time
            # 모든 심사관을 거치지 않아도 mid분 동안 n명 이상의 심사를 할 수 있다면 반복문을 나간다.
            if people >= n:
                break

        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 많거나 같은 경우
        if people >= n:
            answer = mid
            right = mid - 1
        # 심사한 사람의 수가 심사 받아야할 사람의 수(n)보다 적은 경우
        elif people < n:
            left = mid + 1

    return answer