[BOJ] 26단계 이분 탐색

1

1920

수 찾기

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


public class Main {

    private static int[] A;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        A = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(tokenizer.nextToken());
        }
        Arrays.sort(A);

        int M = Integer.parseInt(reader.readLine());
        tokenizer = new StringTokenizer(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < M; i++) {
            int target = Integer.parseInt(tokenizer.nextToken());
            sb.append(binarySearch(0, N - 1, target)).append("\n");
        }
        System.out.print(sb);
    }

    public static int binarySearch(int start, int end, int target) {
        if(start > end){
            return 0;
        }
        int mid = (start + end) / 2;
        if(A[mid] == target) {
            return 1;
        } else if(A[mid] > target) {
            return binarySearch(start, mid - 1, target);
        } else {
            return binarySearch(mid + 1, end, target);
        }
    }
}

*이분 탐색은 탐색하고자 하는 수열이 정렬되어 있어야 한다.

 

2

10816

숫자 카드 2

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


public class Main {

    private static int[] cards;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        cards = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(tokenizer.nextToken());
        }
        Arrays.sort(cards);

        int M = Integer.parseInt(reader.readLine());
        tokenizer = new StringTokenizer(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < M; i++) {
            int target = Integer.parseInt(tokenizer.nextToken());
            sb.append(upperBound(target) - lowerBound(target)).append(" ");
        }
        System.out.print(sb);
    }

    public static int upperBound(int target) {
        int start = 0;
        int end = cards.length - 1;
        int upperbound = -1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(cards[mid] == target) {
                upperbound = mid + 1;
                start = mid + 1;
            } else if(cards[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return upperbound;
    }

    public static int lowerBound(int target) {
        int start = 0;
        int end = cards.length - 1;
        int lowerbound = -1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(cards[mid] == target) {
                lowerbound = mid;
                end = mid - 1;
            } else if(cards[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return lowerbound;
    }
}

*Lower Bound: 정렬된 배열에서 target이 처음 나타나는 위치 (index)

*Upper Bound: 정렬된 배열에서 target을 초과하는 값이 처음 나타나는 위치 (index)

*target의 개수: upperBound(target) - lowerBound(target)

*lowerBound()와 upperBound()는 이분 탐색으로 target을 찾지 못하면 -1을 반환하도록 함

 

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


public class Main {

    private static int[] cards;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        cards = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        for(int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(tokenizer.nextToken());
        }
        Arrays.sort(cards);

        int M = Integer.parseInt(reader.readLine());
        tokenizer = new StringTokenizer(reader.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < M; i++) {
            int target = Integer.parseInt(tokenizer.nextToken());
            sb.append(upperBound(target) - lowerBound(target)).append(" ");
        }
        System.out.print(sb);
    }

    public static int upperBound(int target) {
        int start = 0;
        int end = cards.length;
        while(start < end) {
            int mid = (start + end) / 2;
            if(cards[mid] > target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return end;
    }

    public static int lowerBound(int target) {
        int start = 0;
        int end = cards.length;
        while(start < end) {
            int mid = (start + end) / 2;
            if(cards[mid] >= target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
}

*start, 또는 end가 각각 Lower Bound, Upper Bound가 되도록 함

 

3

1654

랜선 자르기

parametric search: 이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 방법

1. 필요한 랜선의 개수(N)를 만족함

2. 만들 수 있는 랜선의 최댓값

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int K = Integer.parseInt(split[0]);
        int N = Integer.parseInt(split[1]);

        long[] lan = new long[K];
        long max = 0;
        for(int i = 0; i < K; i++) {
            lan[i] = Long.parseLong(reader.readLine());
            max = Math.max(max, lan[i]);
        }

        long MAX = 0;
        long start = 1;
        long end = max;
        while(start <= end) {
            long cnt = 0;
            long mid = (start + end) / 2;
            for(int i = 0; i < lan.length; i++) {
                cnt += lan[i] / mid;
            }
            if(cnt >= N) {
                MAX = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        System.out.print(MAX);
    }
}

*가장 긴 랜선(max)를 기준으로 자른 랜선의 최댓값을 구한다. -> upper bound 방식 (정확히는 upper bound - 1 이 필요)

*입력되는 랜선의 길이가 1cm 이상이므로 이분 탐색의 시작 범위(start)는 1로 설정

*cnt: 이분 탐색의 중간 값(mid) 길이로 다른 모든 랜선을 잘랐을 때 나온 랜선의 개수

*cnt가 필요한 랜선 개수(N)보다 같거나 크면 구하고자 하는 값의 첫 번째 조건을 만족하므로 우선 MAX에 mid를 할당한다.

두 번째 조건을 만족하기 위해 탐색 범위를 mid보다 큰 값에서 탐색을 이어간다.

*cnt가 필요한 랜선 개수(N)보다 작으면 탐색 범위를 mid보다 작은 값에서 탐색을 이어간다.

 

4

2805

나무 자르기

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);
        int[] trees = new int[N];
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int end = 0;
        for(int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(tokenizer.nextToken());
            end = Math.max(end, trees[i]);
        }

        int max = 0;
        int start = 0;
        while(start < end) {
            int mid = (start + end) / 2;
            long cutOff = 0;
            for(int i = 0; i < trees.length; i++) {
                if(trees[i] > mid) {
                    cutOff += trees[i] - mid;
                }
            }
            if(cutOff >= M) {
                max = mid;
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        System.out.print(max);
    }
}