백준 2805번 나무 자르기

문제 링크

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

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다.
(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.
높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

데이터의 범위가 20억까지로 굉장히 크다. 이진 탐색 문제는 데이터의 범위가 굉장히 크게 주어지는 경우가 많다. (일종의 이진탐색으로 풀라고 하는 힌트가 된다.)

나의 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().split('\n')
const target = Number(input[0].split(' ')[1])
const arr = input[1].split(' ').map(Number);

let left = 0;
let right = Math.max(...arr);
let answer = 0
while(left <=right){
  let mid = parseInt((left+right)/2);
  let result = 0
  for(x of arr){
    if(x>mid){
      result += x-mid
    }
  }
  if(result<target){
    //자른 나무가 필요한 나무의 갯수보다 더 작은 경우
    right = mid-1
  }else{
    // 자른 나무가 필요한 나무의 갯수와 같거나 많은 경우
    answer = mid
    left = mid+1
  }
}
console.log(answer)

배운 점

자른 나무의 개수에 따라 right, left를 어떻게 변경해 줘야 할지에만 집중하다 보니
while 문을 언제 탈출해야 할지, 정답을 어떻게 기재해야 할지 놓쳤었다.
1. 자른 나무가 필요한 나무의 개수보다 더 작은 경우
2. 자른 나무가 필요한 나무의 개수와 같거나 많은 경우

같은 경우가 정답이 되는 경우인걸 놓쳐선 안된다.

순차 탐색 vs 이진 탐색

순차 탐색의 시간 복잡도

순차 탐색 : 배열 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인한다.

배열의 index를 따라 순차적으로 탐색할 경우
탐색을 위한 시간 복잡도 : O(N)

이진 탐색의 시간 복잡도

이진 탐색 : 정렬되어 있는 배열에서 탐색 범위를 절반씩 좁혀 가며 데이터를 탐색한다.
탐색을 위한 시간 복잡도 : O(logN)