211019_이진탐색

nais·2021년 10월 18일
0

랜선 자르기

  • K 개의 랜선을 가지고 있음 그 랜선들의 각각의 길이가 주어진 배열 nums {802,743,457,539}
  • 만들고 싶은 랜선의 개수가 매개변서 n으로 주어지는데 이때 랜선의 길이는 최대 얼마로 지정해야하는지를 구하는 문제
  • 우리는 배열을 돌면서 특정 길이(len)으로 배열을 자르면 얼만큼의 개수가 나올지 count()라는 함수로 따로 선언
  • 랜선랜선은 항상 센티미터 정수의 단위 길이로 자른다
    이말은 Math.floor(x)을 사용하여 정수만을 구하라는 의미
    우리는 만약에 300cm 짜리 랜선에서 140 cm 짜리 랜선을 두개 잘라내면 남은 20은 그냥 버리고 가겠다

-> 랜선 2개 !

  • N 개보다 많이 만드는 것도 N개에 포함!

Math.floor(): 소수점 이하 버림 정수만 가쟈감
Math.ceil() : 소수점 이하를 올림
Math.round(): 소수점 이하를 반올림

function solution(nums,n){

  let answer ;

  function count(len){
    let cnt = 0 ; // 랜선의 개수를 카운트 
    for(let x of nums){
    cnt+= Math.floor(x/len); //나눈 정수 값만 랜선으로 치겠다 , 각각의 랜선의 길이를 돌면서 해당 len - 해당 길이로는 nums의 랜선들을 잘랐을 때 총 몇개 나오는지 카운트 
    }
    return cnt;
  }

  // 우리가 반환 할 애들은 최대 길이 이기에 left와 right 도 랜선길이에 초점을 맞춘다 
  let left = 0;

  let right = Math.max(...nums);// 랜선의 길이는 가장 큰 값으로 잡아주겠다  


  while(left<=right){

    let mid = parseInt((left+right)/2);

    // n개보다 많이 만들어주는 값도 n개로 포함되므로 일단 더 크면 값을 반환하는 형태로 선언한다
    // 어차피 계속 mid 값이 구해지면서 answer 의 값도 바뀌기 때문에 
    // 일단 최대한 크게 자르고 점점 줄여가면서 최대치로 값을 찾아보자 
    if(count(mid)>=n){
      answer = mid;
      left = mid + 1 ; //  나오는 랜선의 개수가 n 보다 크다면 우리가 랜선을 짧게 잡고 있다는 ㄷ뜻...! 길이를 길게 해줘야지 랜선의 개수가 줄어든다  
    }
    else{
      right = mid -1 ; // n 보다 값이 작다면 랜선의 길이를 너무 길게 해주고 있는 것이다 자르는  범위를 줄여보자 
    }

  }

  return answer;
  
}

console.log(solution([802, 743, 457, 539], 11));
profile
왜가 디폴트값인 프론트엔드 개발자

0개의 댓글