[프로그래머스 / Java] 입국심사

1. 문제

프로그래머스

 

[문제 요약]

• 모든 사람이 심사를 받는데 걸리는 시간의 최솟값 구하기
• 숫자의 범위가 크다

 

2. 생각대로 풀기

숫자의 범위가 크다 -> 이분 탐색

 

(코드 설명 주석은 AI 활용)

import java.util.Arrays;
class Solution {
   public long solution(int n, int[] times) {
       // n: 입국심사를 기다리는 사람 수
       // times: 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열
       
       // 심사 시간을 오름차순으로 정렬
       Arrays.sort(times);
       
       // 이진 탐색을 위한 범위 설정
       long left = 1;                               // 최소 소요시간
       long right = (long) times[times.length-1]*n; // 최대 소요시간 (가장 긴 심사시간 * 인원수)
       long answer = right;                         // 답을 저장할 변수 (최댓값으로 초기화)
       
       // 이진 탐색 수행
       while (left <= right) {
           long mid = (left + right) / 2;           // 중간값 계산 (현재 검사할 시간)
           
           // mid 시간 동안 n명 이상을 처리할 수 있는지 확인
           if (can(n, times, mid)) {
               answer = mid;                        // 가능하다면 현재 시간을 정답 후보로 저장
               right = mid - 1;                     // 더 작은 시간에서 가능한지 탐색
           } else {
               left = mid + 1;                      // 불가능하다면 더 큰 시간 탐색
           }
       }
       return answer;                              // 찾은 최소 시간 반환
   }
   
   /**
    * 주어진 시간(checkTime) 내에 모든 사람을 심사할 수 있는지 확인하는 메서드
    * @param n 심사해야 할 사람의 수
    * @param times 각 심사관별 심사 시간 배열
    * @param checkTime 검사할 총 소요 시간
    * @return 모든 사람을 심사할 수 있으면 true, 없으면 false
    */
   private boolean can(int n, int[] times, long checkTime) {
       long sum = 0;                               // 심사 가능한 총 인원수
       for (int t : times) {
           sum += checkTime / t;                   // 각 심사관이 checkTime 동안 심사 가능한 인원 누적
           // 심사 가능 인원이 n 이상이면 즉시 true 반환 (최적화)
           if (sum >= n) return true;  
       }
       return sum >= n;                           // 최종적으로 심사 가능 인원이 n 이상인지 확인
   }
}