[JAVA] 이분탐색(Binary Search) & 백준 2512(예산)

이분탐색

크기가 정렬된 배열의 중간에 위치한 값부터 탐색해 왼쪽이나 오른쪽 부분에 있는 내가 원하는 값을 알아내는 것이다.
(데이터 삽입이나 삭제가 빈번하면 시간복잡도만 높이고 효율이 떨어지는 탐색이므로 데이터가 고정된 상황에서 사용해야 한다.)

구현방법

• 고정된 데이터가 정렬되어 배열에 있어야 한다.
• start, end(또는 min, max)로 mid를 찾는다. (mid = (start+end) / 2)
• mid 값과 내가 원하는 key 값 비교
  • mid > key : end = mid-1(왼쪽 반에서 다시 탐색하기 위해 위치 조정)
  • mid < key : start = mid+1(오른쪽 반에서 다시 탐색하기 위해 위치 조정)
  • mid == key : 찾음 리턴!
• start < end일 경우 계속 반복해 원하는 값 찾기

• 아마 말로 설명하는 것보다 실제 문제를 같이 풀어보는 것이 이해가 훨씬 빨리 될 것이다.
  => 그래서 백준 문제(2512)를 풀어보겠다.
  https://www.acmicpc.net/problem/2512

<문제>

1. 모든 요청이 배정될 수 있는 경우 요청 금액 그대로 배정
2. 모든 요청이 배정될 수 없는 경우 특정한 정수 상한액을 계산해 그 이상인 예산요청에는 모두 상한액을 배정 / 이하는 요청한 금액 그대로 배정

⇒ 이 조건을 만족하도록 예산을 배정하는 프로그램 만들기

<입력>

#1: 지방의 수 N(3~10,000)
#2: 각 지방의 예산 요청 N번(1~1,000,000)
#3: 총 예산 M(1,000,000,000)

4
120 110 140 150
485

<출력>

127

<풀이>

• 까다로운 조건이 존재하지 않는 단순 이분 탐색이다.
• 먼저 입력값을 모두 받아 저장
• while문을 돌며 계산한다.
  • key < M ⇒ min = mid+1 (오른쪽 반에서 다시 계산 시작하겠다)
  • key > M ⇒ max = mid-1(왼쪽 반에서 다시 계산 시작하겠다)
• 반복이 끝난 후 max값 출력

=> 이 풀이대로 아래 코드를 작성하였다. 혹시라도 이 풀이가 이해가 안된다면 주석을 읽어 바로 이해할 수 있을 것이다.

<전체코드>

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

public class bs_2512 { //예산
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr); //오름차순 정렬
        int M = Integer.parseInt(br.readLine()); // 총 예산
        int min = 0; //최솟값
        int max = arr[N-1]; //최댓값
        while(min <= max) {
            int mid = (min+max) / 2;
            long sum = 0;
            for(int i=0; i<N; i++) {
                if(arr[i]>mid) sum += mid;
                else sum += arr[i];
            }
            if(sum <= M) min = mid + 1; //예산이 작게 배정된 것이므로 min을 높인다. 오른쪽 반에서 다시 계산하기 위해서
            else max = mid - 1; //예산이 크게 배정된 것이므로 max를 줄인다. 왼쪽 반에서 다시 계산하기 위해서
        }
        System.out.println(max); //while문이 끝나면 계산이 모두 끝난 후 max가 min보다 작아지므로 max 출력
    }
}