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

입국심사는 심사시간이 다른 m명의 심사위원이 n명의 사람들을 심사하여 모두 통과시키는데 걸리는 최소 시간을 찾는 문제이다.

풀이

이분 탐색을 이용하여 최소 시간을 구한다.
주의할 점은, 이분탐색의 오른쪽에 최대 시간을 잡는 과정이다. 문제의 제한조건은 다음과 같다.

심사받는 사람의 수 = (1,1000000000)
심사 시간의 범위 = (1,1000000000)
심사위원의 수 = (1,100000)

n명의 심사받는 사람이 m명의 심사위원에게 심사를 받는다고 가정했을 때, 쉽게 생각할 수 있는 최대값은

MAX_VAL = n * MAX(심사위원의 심사시간) / 심사위원의 수

이다.

이를 기준으로 코드를 작성하면, 다음과 같다.

코드

 function solution(n, times) {
    var answer = 0;

    times.sort((a,b) => a - b); 
    
    //right 범위 설정(최대 심사인원 * 최대 입국심사 시간 / 심사위원 수)
    var right = Math.floor((times[times.length - 1] * n) / times.length);
    var left = 1;
    
    while(left < right){
        var mid = Math.floor((left + right) / 2);
        
        var tmpTime = 0;
        for(let i = 0; i < times.length; i++){
            tmpTime += Math.floor(mid / times[i]);
            if(tmpTime >= n) break;
        }
        if (tmpTime >= n) {
            right = mid;
        }
        else left = mid + 1;
    }
    
    answer = right;

    return answer;
}

배운 점

1. Left, Right의 범위

문제마다 이분탐색을 사용하는 범위가 달라진다는 점을 배웠다. 위 문제에서 예시가

n = 6
times = [7,10]

로 나왔는데, 알고리즘을 대충짜서 28, 29초 둘다 7이 나와 구분을 할 수 없는 불상사가 생겼다. 그래서 n과 tmpTime의 값이 같을 때도 right의 값을 줄여 최소를 갖게 만들었다.

그랬더니 right의 값이 정답을 지나쳐서 왼쪽으로 가는 경우가 생겼다. 그래서 결국

right = mid - 1 => right = mid

로 바꿔주었다.

2. Loop Performance

처음에는 for-of 구문을 사용하여 문제를 풀었는데, 퍼포먼스가 너무 낮게 나왔다. (물론, Mid를 구하는 과정에서 2를 나눠주지 않은 것 때문이었다.. 실수를 줄이자.)

처음에는 몰랐기 때문에 for-of의 성능 문제라고 생각하여, 일반적인 for문으로 바꿔주었다. for의 반복문은 일반적인 for문이 가장 빠르다는 것을 알았다.

3. Javascript Sort

자바스크립트에서는 일반적으로 sort에 compare 함수를 입력하지 않으면 string을 기준으로 정렬한다. 정렬 기준이 string의 경우, [7, 10]의 예시에서 1이 사전 순으로 작기 때문에 [10, 7] 의 순서로 정렬한다. 이를 피해 숫자 크기 순으로 정렬하기 위해 코드를 다음과 같이 변경했다.

	// Before
	array1.sort();

	// After
	array1.sort((a,b) => a - b);

참고 자료

문제: https://school.programmers.co.kr/learn/challenges?order=acceptance_desc&page=1

반복문 성능 비교: https://gurtn.tistory.com/121

정렬: https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

잘못된 부분이 있다면 댓글에 남겨주시면 감사하겠습니다.