[프로그래머스 / Java] 입국심사 (Lv.3)

문제 풀이 날짜: 2023.09.18
포스트 작성일: 2023.09.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

프로그래머스 : 입국심사 (Lv.3)

 

키워드

이분 탐색

 

풀이 접근법

• 이분탐색은 탐색 범위를 좁혀가면서 최댓값&최솟값 또는 근사치를 찾을 때에 유용하게 사용된다.
• “모든 사람이 심사를 받는 데 걸리는 시간의 최솟값”의 의미
  
  • 검사를 완료한 사람이 n명에 다다를 때까지 반복하고 그 lower bound를 구한다.
  • 누적 소요 시간이 k초일 때 이를 각 검색대 별 소요 시간으로 나누어보면 검사를 마친 인원 수가 계산된다.
  • 검사 완료된 인원수가 [n - 1, n - 1, n, n, n, n, n + 1, …] 이라면 n이 처음 출현한 시간을 구해야 함 ⇒ 이것이 최소 시간
  • 굳이 여러 구간을 동시에 탐색하지 않아도 현재까지의 경과 시간을 각 검색대별 시간으로 나눠보면 각 검색대별로 심사를 마친 인원을 모두 구할 수 있다.
  • 시간이 빠른 순서부터 검사를 받아보아야 하므로 입력 배열을 정렬한다.
•  이분탐색의 start와 end는 무엇으로 정의하는 게 좋은가?
  • 각 검색대 별로 가장 짧은 소요시간부터 (검색대의 최대 소모 시간 × 인원수)까지 탐색한다.
  • 탐색을 멈추는 key 값은 모든 검색대에서 심사를 마친 인원수이다. (key == n)
• 주어진 입력들의 합을 구하다보면 오버플로우가 날 위험이 있으므로 변수를 long타입으로 선언하여 푼다.

 

코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;
        
        Arrays.sort(times);
        
        long start = times[0];
        long end = times[times.length - 1] * (long)n;
        
        while(start <= end) {
            //오버플로우 발생 가능(1)
            long mid = start + ((end - start) / 2);
            
            long sum = 0;
            for(int t : times) {
                long numOfPeople = mid / t; //오버플로우 발생 가능(2)
                sum += numOfPeople;
            }

            if(sum >= n) { //lower bound를 찾으며 범위를 좁힌다
                answer = Math.min(answer, mid);
                end = mid - 1;
            }
            else { //(sum < n)
                start = mid + 1;
            }
        }
        
        return answer;
    }
}

---

 

 

참고한 링크

https://suhyeokeee.tistory.com/183