BOJ 2512 with js _ 예산

2512 with Node.js _ 예산

문제

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

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

예를 들어, 전체 국가예산이 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 이하이다.

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다.

정답 코드

const fs = require("fs");
const stdin = (
  process.platform === "linux"
    ? fs.readFileSync("/dev/stdin").toString()
    : `` // 기본 입력값 설정 (백준 코딩테스트에서 비워놔도 무방하다.)
).split("\n");

const input = (() => {  //input()을 호출할 때마다 한줄씩 읽어온다.
  let line = 0;
  return () => stdin[line++];
})();

const regionCount = +input();
const requestedBugets = input().split(' ').map(v => +v).sort((a,b) => a-b);
const totalBuget = +input();

function getBuget(maxBuget){ // maxBuget을 설정했을 때 소요되는 예산값 구하는 함수
  return requestedBugets.reduce((prev,cur) => prev + Math.min(maxBuget,cur),0);
}

function binarySearch(target, start, end){ // 빠르게 해당 값을 구하기 위해서 이분 탐색 함수
  if(start > end){
    return end; // 정확히 떨어지는 값을 찾지 못했을 경우는 제일 적게 남는 값으로 반환
  }
  const middle = Math.floor((start+end)/2);
  const middleBuget = getBuget(middle);
  if(middleBuget == target){
    return middle; // 예산이 정확히 떨어지는 값을 찾으면 반환
  }

  if(middleBuget < target){
    return binarySearch(target, middle + 1, end);
  } else {
    return binarySearch(target, start, middle - 1);
  }
}

var result = binarySearch(totalBuget, 1, requestedBugets[regionCount -1]);
console.log(result); // 결과 값 출력

살펴보아야 할 점

Binary Search 이분탐색

https://www.geeksforgeeks.org/binary-search-in-javascript/

탐색의 시간을 줄이는 알고리즘 중에 이분탐색은 while문을 이용하거나 재귀함수를 이용하여 구현가능하다. 시간 복잡도 또한 logN으로 훌륭하다.

문제 링크

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

-- 참고자료 --

간단한 while문을 이용한 이분 탐색! https://jwoop.tistory.com/9

while(left <= right) { // 간단한 while문 이용한 이분탐색
    let mid = Math.floor((left+right)/2);
    
    if(mid == target){
        return mid // answer
    }
    
    if(target > mid){
        left = mid + 1;
    } else {
        right = mid - 1;
    }    
}