[프로그래머스] 입국심사 (Javascript)

코딩테스트 연습 - 입국심사 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

---

난이도 : Level 3

 

풀이과정 :

맨 처음에 이 문제를 봤을 땐 이걸 이분탐색으로 어떻게 풀어야 될지 감이 안왔는데

그 이유가 나는 n을 기준으로 time의 각 요소에 얼마를 곱해야 되는지 생각을 해서 풀이가 어려웠다.

생각을 반대로 times를 기준으로 계산한 값이 n이 될 수 있을 때를 생각을 해보면

이분탐색으로 풀 수 있구나를 생각할 수 있었다.

 

그 후 이분 탐색 코드를 작성하다보니

이분탐색을 위해 left = 1이 되는 것은 자명했고, right의 값이 최대 몇이 될 수 있을지에 대해 고민했다.

times배열을 정렬하고, times[times.length-1]*n이 최대값이라고 생각을 해봤는데, 

뭔가 더 작아도 될 거같아서 tims[0]*n 이라고 했는데 테스트를 통과했다. 

생각해보면 times[0]*n보다는 정답이 더 작다는 건 대충 알거같긴 한데.. 아리쏭하다

명확하게 수학적으로 표현하지는 못하겄다..

 

그 다음 mid / time 요소들의 값을 cnt 에 더해주면서 이분탐색을 돌려준다.

이 때 주의해야할 부분은 cnt가 정확하게 n이 될 수 없는 경우도 있다는 것 !!!!!!!!!!!

이 부분을 놓쳤다면 아마 테스트케이스 6, 9 번에서 에러가 날 것이다.

 

10

[ 6, 8, 10 ]

위 테스트케이스는 답은 30이다. 

이분탐색을 돌려보면 cnt가 정확하게 10이 되는 경우가 없다.

이 부분을 고려해서 코드를 짜면 아래와 같다.

 

function solution(n, times) {
    var answer = 0;
    times.sort((a,b) => a-b);
    
    let l = 1;
    let r = n*times[0];
    
    while(l<=r){
        let m = Math.floor((r+l)/2);      
        let cnt = 0;
        for(e of times){
            cnt += Math.floor(m/e);
            if(cnt > n) break; // cnt 오버플러우 방지
        }
        
        if(cnt<n){
            l = m+1;
        }else{
            r = m-1;
            answer = m;
        }
    }   
    return answer;
}