이진 탐색 문제풀이(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가 개선해준 코드를 통해 , 최대한 시간 복잡도를 고려해서 안 써도 되는 코드들은 줄일 수 있는 방향으로 해봐야겠다.