프로그래머스: 징검다리 건너기 - javascript(이분탐색)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/64062

문제 풀이 힌트 

 

단순하게 반복문으로,

1) 현재 디딤돌 배열로 사람 하나 건널 수 있는지 체크 

- 디딤돌 숫자가 0인 것이 연속적으로 k이상이 되면 못건넘 

2) 건넜다면 각 디딤돌 숫자 -1 , 건넌 사람 수인 cnt + 1

3) 건너지 못했다면 그동안 건넌 친구 cnt return 하기 

 

의 방법을 생각했다면 바로 시간 초과다. 

 

 

stones 배열의 크기도 엄청난데, 디딤돌 숫자가 2억까지도 가능하다니,,, 

그러면 모든 디딤돌이 2억일 때, 

나는 각 배열에서 사람 하나 건널 때 -1을 2억번 해야 한다. 

 

단순 반복문으론 어림도 없다.

 

자, 이분탐색으로 시선을 바꿔보자. 

 

단순 반복문으로 생각할 때는 기준이 '디딤돌'이 된다.

그러나, 이분 탐색에서는 기준이 '사람'이 된다. 

 

 

이 제한 조건에서 사람이 건널 수 있는 예상 가능한 최대 값은 몇명인가?

모든 stones가 200,000,000인 경우다. 

즉, 사람은 200,000,000 명 건널 수 있다. 최대로 ! 

 

사람이 건널 수 있는 최소 값은 몇명? 0 명 ! 

 

1) 최솟값과 최댓값의 중간 값 mid 를 구한다. 

2) 이 mid로 현재 디딤돌을 건널 수 있는지 확인한다. 

- 직접 stones 배열에서 mid 값을 빼야 한다. 

- 이때, 0 이하인 숫자 디딤돌이 몇번 연속되는지 체크해준다. 

- 만약 0이하 디딤돌 연속 숫자가 === k 가 되는 순간 flag = true로 만들어준다. 

3) flag === true 라면 , right = mid-1 이 된다. (현재 사람 숫자도 못 건너니 더 큰 사람 숫자는 볼 필요도 없다.)

4) flag === false라면 , left = mid+1이 된다. (현재 사람 숫자를 건너니 더 작은 숫자는 볼 필요도 없다. )

 

정답 풀이 코드 

function solution (stones, k) {
  let left = 1;
  let right = 200000000;
  
  while(left <= right) {
    const mid = Math.floor((left + right)/2); 
    let count = 0;
    for(let i = 0; i < stones.length; i++){
    if(stones[i]-mid <= 0) count++; 
      else count = 0; 
      if(count >= k) break;    
    }
    if(count >= k) right = mid - 1; 
     else{
         left = mid + 1; 
     }
  }
  return left;
}

Only 풀이 코드 

function solution (stones, k) {
  let left = 1;
  let right = 200000000;
  
  while(left <= right) {
    const mid = Math.floor((left + right)/2); 
    let count = 0;
    for(let i = 0; i < stones.length; i++){
    if(stones[i]-mid <= 0) count++; 
      else count = 0; 
      if(count >= k) break;    
    }
    if(count >= k) right = mid - 1; 
     else{
         left = mid + 1; 
     }
  }
  return left;
}

알고가는 ppoint 

- 반복문인데, 효율성문제다? 

=> 이분 탐색부터 생각하자. 

  - 대신 기준을 바꿔서도 생각해봐야 한다. (디딤돌 기준 => 사람 기준 )