백준 2805 나무자르기 - node.js

해당 포스팅은 백준 2805번 나무자르기 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

문제

• 상근이는 나무 M미터가 필요하다.
• 상근이는 목재절단기로 나무를 자를 것이다.
  목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다.
  따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.
• 예제:
  한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17.
  상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 총 7미터를 집에 들고 간다. 절단기에 설정할 수 있는 높이는 0 이상이다.
• 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하자.

입력

1. [첫째 줄] : 나무의 수 N, 상근이가 집으로 가져가려고 하는 나무의 길이 M
   (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

2. [둘째 줄] : 나무들의 높이
   나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.
   (0 <= H <= 1,000,000,000)

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

풀이

N과 M이 각각 10만, 20만이므로 BF로 풀면 시간 초과이다. 이분탐색으로 풀어보자.

아래 예제로 설명을 하겠다.

4 7
20 15 10 17

1. input의 첫 번째 줄은 NM, 두 번째 줄은 trees로 설정하자.

   • N : 나무의 개수 4
   • M : 가져가고자 하는 나무 길이 7
   • trees: 나무 배열 [20, 15, 10, 17]

2. 이분탐색 하기 위해 trees를 오름차순 정렬한다. [10, 15, 17, 20]

3. 이분탐색 함수 binarySearch를 구현한다.
   • binarySearch 함수는 trees와 M, start, end를 매개변수로 받는다.
   • 높이의 최댓값을 저장할 answer를 정의한다.
   • start <= end까지 while문을 돌리면서 answer를 구한다.
     • while문 안에서 mid를 구한다. 이 때 mid는 Math.floor((start + end) / 2)로 절단기의 위치이다.
     • trees를 순회하면서 얻을 수 있는 나무를 더해주어 총합을 구한다.
     • if 총합이 M보다 클 시, mid >= answer라면 업데이트를 해준다(그 이유는 높이의 최댓값을 구하므로 이분탐색으로 업데이트해주어야 한다).
       그 다음 절단기 높이를 높여주기 위해 start를 mid + 1로 옮겨준다.
     • else 총합이 M보다 작을 시, 나무가 부족한 것이므로 절단기 높이를 낮추기 위해 end를 mid - 1로 옮겨준다.

4. 이분탐색 함수를 호출해 값을 구한다.
   binarySearch(trees, M, 0, trees[trees.length - 1])

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [NM, trees] = input.map((el) => el.split(" ").map((val) => +val));
const [N, M] = NM;

trees.sort((a,b) => a-b);

function binarySearch(arr, M, start, end) {
    let answer = Number.MIN_SAFE_INTEGER;
    while(start <= end) {
        let mid = Math.floor((start+end) / 2);
        let sumTree = arr.reduce((prev, curr) =>{
            let cutTree = curr - mid;
            return prev = (cutTree > 0) && (prev + cutTree)
        }, 0);
        if (sumTree >= M) {
            if (mid > answer) answer = mid;
            start = mid + 1;
        }
        else {
            end = mid - 1;
        }
    }
    return answer;
}

console.log(binarySearch(trees, M, 0, trees[trees.length - 1]));