이진 탐색 문제풀이(feat:백준 예산)

예산

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

문제
국가의 역할 중 하나는 여러 지방의 예산 요청을 심사하여 국가의 예산을 분배하는 것이다. 국가 예산의 총액은 미리 정해져 있어서 모든 예산 요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총예산을 다음과 같은 방법으로 배정한다.

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

예를 들어 전체 국가 예산이 485이고, 4개 지방의 예산 요청이 각각 120, 110, 140, 150이라고 하자. 이 경우 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고, 그 합이 484로 가능한 최대가 된다.

여러 지방의 예산 요청과 국가 예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력
첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산 요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그다음 줄에는 총예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다.

나의 풀이 방향 및 코드

(1) 제일 작은 예산을 최솟값으로 잡는다.

(2) 제일 큰 예산을 최댓값으로 잡는다.

(3) 작은 수와 큰 수의 중간점을 기준으로 이진 탐색 알고리즘을 실행한다.

(4) 최적의 결론을 도출한다.

/*
N: 지역의 수
array: 각 지역의 예산 요청액
moneyAll: 예산 총액
*/
function solution1(N, array, moneyAll) {
  // 오름차순 정렬
  array.sort((a, b) => a - b);

  // 제일 작은 예산 기준
  let left = array[0];

  // 제일 큰 예산 기준
  let right = array[N - 1];

  let answer = left;

  while (left <= right) {
    // 중간값부터 잡기
    let mid = Math.floor((left + right) / 2);

    let totalCount = 0;

    // mid 확인
    for (let i = 0; i < array.length; i++) {
      if (array[i] >= mid) {
        totalCount += mid;
      } else {
        totalCount += array[i];
      }
    }

    // 여기서 예산이 초과되면
    if (totalCount > moneyAll) {
      right = mid - 1;
    } else {
      answer = mid;
      left = mid + 1;
    }

    // 예산이 딱 맞거나 미만이면
  }

  console.log(answer);
}

solution1(4, [120, 110, 140, 150], 485);

---

GPT 개선 코드

function solution(N, array, moneyAll) {
  let left = 0; // 상한액의 최솟값
  let right = Math.max(...array); // 상한액의 최댓값은 예산 요청 중 최댓값

  let answer = 0;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    let total = 0;

    // 예산을 mid로 배분
    for (let i = 0; i < N; i++) {
      total += Math.min(array[i], mid); // 요청 금액과 상한액 중 작은 값을 더한다.
    }

    if (total > moneyAll) {
      // 예산을 초과하면 상한액을 줄인다.
      right = mid - 1;
    } else {
      // 예산이 충분하면 상한액을 높인다.
      answer = mid; // 가능한 상한액 저장
      left = mid + 1;
    }
  }

  return answer;
}

개선 사항

• 정렬 제거: 정렬이 필요 없으므로 array.sort() 대신 Math.max(...array)를 사용하여 상한액의 최댓값을 계산합니다. 이로 인해 시간 복잡도가 O(N log N)에서 O(N)으로 줄어듭니다.

• Math.min 사용: if-else 구조 대신 Math.min(array[i], mid)를 사용하여 코드 가독성을 개선하고 연산을 더 직관적으로 표현합니다.

정리 및 마무리

• 이진 탐색 알고리즘에 대해서는 좀 더 익숙해졌다.
• GPT가 개선해 준 코드를 통해 최대한 시간 복잡도를 고려해서, 사용하지 않아도 되는 코드는 줄이는 방향으로 작성해야겠다고 생각했다.