[프로그래머스 / js / 이분탐색] 입국심사

문제

입국심사대에 따라 심사하는데 걸리는 시간은 다르며 한 심사대에서는 동시에 한명만 심사가 가능하다.  

가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다. 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구해라

 

ex)

n                          times                   return

6

[7,10]

28

n(심사를 받는 사람 수) , times배열(각 심사관이 한명을 심사하는데 걸리는 시간)

 

제한사항

n은 1 ~ 1000000000
각 심사관이 한명을 심사하는데 걸리는 시간 1 ~ 1000000000분
심사관은 1 ~ 100000명

 

첫풀이

 

이분탐색 문제인 걸 알고 풀기 시작했지만 처음이라 어떻게 접근해야할지를 몰랐다 그래서 처음에는 기다리는 시간에 입국심사 받는 시간을 더하는 값이 가장 작은 경우를 n까지 반복문을 돌아 누적값을 구했다. 몇개만 맞고 당연히도 시간 초과가 나버렸다ㅎㅎ..

function solution(n, times) {
  var answer = 0;
  times.sort((a, b) => a - b);
  leftTime = Array.from(times);
  while (n > 0) {
    let min = Math.min(...leftTime);
    let min_idx = leftTime.indexOf(min);
    answer = leftTime[min_idx];
    leftTime[min_idx] += times[min_idx];
    n--;
  }
  return answer;
}

 

 

이분탐색

우선 이분탐색이 무엇일까?

정렬되어 있는 배열에서 탐색 범위를 절반씩 두 부분으로 나눠 필요 부분으로 범위를 좁혀가며 찾는 알고리즘이다. 

start = 0

end = 배열의 마지막 index

mid = (left+right)/2 

function binarySearch(arr, target) {
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    mid = ~~((start + end) / 2);
    console.log("mid", mid);
    if (target === arr[mid]) return mid;
    else if (target < arr[mid]) end = mid - 1;
    else {
      start = mid + 1;
    }
  }
  return -1;
}

 

이렇게 보면 이분탐색 문제는 쉬울 것 같았는데 막상 문제를 보면 이분탐색으로 풀 방법이 떠오르지가 않았다ㅜㅡㅜ

 

고민하다가 도저히 모르겠어서 푸신분들의 코드를 참고하여 풀게 되었다!

이분탐색 풀이

 

가장 짧은 시간을 1, 가장 오래걸리는 최대시간을 입국심사 시간 중 최대인값 * n 으로 지정하고 이분탐색을 통해 풀어주었다.

 

mid값을 입국심사 시간들로 나눈 값들을 더해 count를 구한다.

(mid시간 동안 몇명을 심사할 수 있는지 구하는 것!)

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하는 것이니 count값이 n보다 크거나 같다면 answer과 비교해 min값을 저장해준다

count값이 더 컸다면 더 작은 값을 확인해봐야하므로 right=mid-1, 작았다면 left=right+1로 해주며 반복문을 모두 돌아 결과를 얻는다!

function solution(n, times) {
  var answer = 0;
  times.sort((a, b) => a - b);
  let right = times[times.length - 1] * n;
  let left = 1;
  answer = right;
  while (left <= right) {
    let count = 0;
    let mid = Math.floor((left + right) / 2);
    times.map((time) => {
      count += Math.floor(mid / time);
      if (count >= n) answer = Math.min(answer, mid);
    });
    if (count >= n) right = mid - 1;
    else left = mid + 1;
  }
  return answer;
}

++
내가 소수점을 버릴 때 Math.floor 대신 ~~ 비트연산자를 사용하는데 이번 문제에서는 비트연산자를 사용할 경우 시간 초과가 났다
원인을 몰랐는데 찾아보니 비트 연산을 사용해서 소수점을 삭제하면 32비트만 남기 때문에 범위를 초과하는 경우 이상한 값으로 mid값이 설정이 되어 시간 초과가 난다고한다..!! 32비트가 표현할 수 있는 숫자가 약 40억까지인데 이 문제 제한사항을 보니 그 이상인 값이 들어가는 경우가 있을 것 같다 비트 연산자는 앞으로 범위를 잘 보고 사용해야겠다!

이분탐색 문제를 많이 풀어봐야겠다는 생각을 하게 해준 문제다 앞으로도 화이팅 >!!