백준 js 2805번

 

<백준 문제>

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

2805번: 나무 자르기

 

 

 

 

 

<적용한 알고리즘 정리>

 

- 이분 탐색 - 

1. 정렬되어 있는 리스트(배열)에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
2. 조건이 있는데 배열에 있는 데이터가 정렬되있어야 한다.
3. 변수 3개(start, end, mid)를 이용하여 찾으려는 데이터와 중간에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾을때 까지 진행한다.
4. 중간값과 찾고자 하는 값을 비교해서 찾고자 하는 값이 중간값보다 작으면 중간값 기준 왼쪽을
   크면 중간값 기준 오른쪽을 탐색한다. 

 

 

<문제 핵심>

 

1. 높이가 나열 되있는 배열은 정렬 되있어야 한다.
2. 로직을 통해 구한 중간 값 만큼 나무의 높이를 잘랐을 때 조건을 만족하면
   (잘린 나무의 길이의 합이 7 이상이면) start의 값을 조정한다.
   -> 중간값보다 큰 숫자들을 대상으로 이분탐색을 진행한다.( 탐색범위의 단축 )
   -> 만약 조건이 만족 안됬다면 end의 값을 조정한다.( 탐색범위의 단축 )

 

 

<풀이방법 및 순서도>

 

1. 나무의 갯수와 가져가야 되는 나무의 높이를 구조분해할당을 통해 가져온다
2. 높이를 담고 있는 배열에 오름차순 정렬을 적용한다.(이분탐색의 핵심: 오름차순 정렬)
3. 이분탐색의 로직을 구현하는 함수를 만들고 start값, end값을 구하여 mid값을 구한다.
4. for of 반복문을 돌면서 배열의 높이보다 mid값이 작으면 각 배열의 높이에 mid값을 빼주고
   빼준 값 만큼 sum 변수에 누적하여 합을 구한다.
5. sum의 값이 가져가야 되는 높이 기준을 만족했는지 안했는지에 따라 start = mid+1,
   end = mid - 1을 함으로써 탐색 범위를 좁혀준다.
   ✨해당 과정을 통해 start > end가 되면 while문을 탈출하고 이후 answer값이 console로 출력된다.

 

 

<최종 코드>

 

let input = require("fs")

  .readFileSync(0, "utf-8")

  .trim()

  .toString()

  .split("\n");

const [N, M] = input.shift().split(" ").map(Number);

const sortedArray = input[0]

  .split(" ")

  .map(Number)

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

//N: 나무의 갯수 M: 가져가야하는 높이

function solve(sortedArray, target) {

  let start = 0;

  let end = sortedArray[sortedArray.length - 1];

  let answer = 0;

  while (start <= end) {

    let mid = Math.floor((start + end) / 2);

    let sum = 0;

    for (let x of sortedArray) {

      if (x > mid) sum += x - mid;

      //x >= mid 안해주는 이유는 0은 차피 안더해줘도 되기 때문

    }

    if (sum >= target) {

      if (mid > answer) answer = mid;

      // 최댓값 계속 구해주기.

      // 이 부분을 제외하고는 일반적인 이분탐색 코드와 똑같다.

      start = mid + 1;

      //start가 11이고 end 20이므로 mid구하면 15가 됌

    } else {

      end = mid - 1;

    }

  }

  return answer;

}

console.log(solve(sortedArray, M));