백준 1300: k번째 수 - javascript(이진탐색)

문제 출처 

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

 

정답 풀이 

 

일단 이 논리를 알고가자 

주어진 배열에서 8이하인 수가 몇개 있을까? 

 

 

결론부터 말하면 

8이라는 숫자를 각 배열의 idx값으로 나는 몫을 다 더한 개수가 된다. 

idx가 1인 배열을 봐보자. 8/1을 하면 몫이 8이 된다. 그런데 애초에 가로 배열 크기가 4가 최대니까 값이 4가 된다. 

...

idx가 4인 배열을 봐보자. 8/4를 하면 몫이 2가 된다. 실제로 8이하인 수의 개수는 4와 8 두개이다. 

 

 

왜 이런 논리가 들어맞는걸까? 

사실 각 idx로 나눠준 것은 각 가로 배열의 첫번째 숫자를 의미한다. 

idx === 배열 첫번재 숫자가 같다.  

 

그리고, 해당 가로 배열을 보면, 해당 숫자만큼 계속 커지는 규칙을 확인할 수 있다. 

 

그러니, 각 가로 배열에서 8이 언제쯤 나올지 예측할 수 있게 된다. (안나올 수도 있다) 

정리하자면) 

8보다 작은수가 몇개인지 알 수 있다는 뜻이다. 

8을 해당 숫자 (idx) 로 나눈 몫이 된다. 

 

일단 이것을 알고가면 50%는 이해가 된 것이다. 

그다음을 살펴보자. 

 

우리가 구해야 하는 k번째 수가 7이라고 가정하자. 

 - 이 의미는 k 이하의 수는 7개라는 것을 의미한다. 

 

k번째 수가 될 수 있는 후보는 1부터 16이 된다. 

- 즉, start = 1 , end = n*n 이 된다. 

 

그리고 mid 값은 처음에 8이 될 텐데, 아까 우리는 8이하의 수의 개수를 구해놨다. 

=> 12개였다. 

- 이뜻은 뭐다? 8이하인 숫자의 개수는 12개라는 뜻이다.  

아래 배열 확인해보면 실제로 그렇다. 

[1,2,2,3,3,4,4,4,6,6,8,8,9,12,12,16] 

 

그런데 우리는 7번째 숫자가 궁금하니,  

범위를 왼쪽으로 좁혀야된다. 

end = mid - 1 이 되겠다. 

 

이런식으로 진행하면 된다 

정답 코드 

const [n,k] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n').map(v => +v); 

function solution(n,k){
    let start = 1; 
    let end = n*n; 
    
    while(start <= end){
       let mid = parseInt((start + end)/2)
       let cnt = 0; 
       for(let i=1; i<=n; i++){
          cnt += Math.min(Math.floor(mid/i), n)
       }
        if(cnt < k){
          start = mid + 1 
        }
        else{
            end = mid - 1
        }
    }
  return start
}


console.log(solution(n,k))