LEVEL 3 : 입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

• 문제

  • 

    문제

---

풀이

• 이분 탐색 문제이다( 조건의 보면 범위가 time은 최대 10억 , 한 명을 검사하는데 기다리는 사람은 최대 10억 명이기 때문에 최악의 경우에는 10억 * 10억 이 될 수 있으므로 이분 탐색으로 검색하여야 한다.)
• 0 ~ 10억 * times의 최댓값 범위의 값을 이분 탐색하며 해당 시간일 때 최대될 수 있는 사람 수를 구한다.
  • 만약 최대 될수 있는 사람이 n 보다 크거나 같을 경우 최댓값( end) 범위를 mid -1로 설정
  • 만약 최대 될수 있는 사람이 n 보다 작을 경우 최솟값 (start) 범위를 mid + 1로 설정
  • 코드를 보면 이해가 쉬울 것이다.

• public static long solution(int n, int[] times) {
         long answer = Long.MAX_VALUE; // 정답 초기화
         long start = 0; //시작 범위 0 
         long end = (long)1000000000 * (long)Arrays.stream(times).max().getAsInt();// 종료 범위 10억 * time의 최댓값
         Arrays.sort(times);
         while(start <= end) {//이분 탐색 시작
          long mid = (start + end)/2; // 중간 값 설정
          long sum = 0;// mid 시간이었을 때의 몇 명의 사람을 처리했는지 계산
          for(int i=0;i<times.length;++i) { // times 배열을 돌면서 
          sum += mid/times [i];//하나의 카운터에서 처리한 횟수를 sum에 더해줌
          }
          if(sum >= n) {// 만약 mid시간이 었을 때의 처리한 사람이 n 보다 크다면
          end = mid - 1; // end 범위 축소 -> end를 mid - 1로 설정한다.
          answer = Math.min(mid, answer); // 이 경우 n 명보다 많이 처리할 수 있으므로 정답이 존재
          } else {
          start = mid + 1;//start 범위 축소 -> start를 mid +1로 설정
          //이 경우에는 정답이 될 수 없으므로 answer 최솟값 계산할 필요 없다
          }
         }
         return answer;
  	}