[코딩테스트] Java 입국심사

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

이분탐색을 이용하여 심사가 끝나는 시간을 기준으로 처리 가능한 총 인원을 계산하여 n보다 클 때에 값을 갱신하는
lowerbound(특정 조건을 만족하는 값 중에서 최솟값)를 사용했습니다. 

소스코드

import java.util.*;

class Solution {

    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = 0;
        long left = 1;
        long right = (long)times[times.length-1] * n; // 60
        
        while (left <= right) {
            long mid = (left + right) / 2; // 중간 시간
            long peopleProcessed = 0;

            // mid 시간 동안 처리 가능한 총 인원 계산
            for (int time : times) {
                peopleProcessed += mid / time;
                if (peopleProcessed >= n) break; // n명을 초과하면 더 계산할 필요 없음
            }

            if (peopleProcessed >= n) {
                answer = mid; // 더 작은 시간을 탐색
                right = mid - 1;
            } else {
                left = mid + 1; // 시간을 더 늘림
            }
        }

        return answer;
    }
}

코드 설명

• 변수 초기화
  • times: 각 심사대의 심사 시간이 들어있는 배열. 이 배열은 오름차순으로 정렬됩니다.
  • left: 가능한 시간의 최솟값 1입니다.
  • right: 최악의 경우 가장 느린 심사관이 n명을 모두 처리하는 시간(times[times.length-1] * n) 입니다.
• 이분탐색
  • mid: 현재 탐색 중인 시간입니다.
  • peopleProcessed: mid 시간 동안 각 심사관이 처리할 수 있는 총 인원 수를 계산합니다.
• mid 시간 동안 처리 가능한 인원 계산
  • mid / time: 각 심사관이 mid 시간 동안 처리 가능한 사람 수.
  • 총 처리 인원(peopleProcessed)이 n명을 넘으면 반복문을 종료합니다.
• 조건에 따라 탐색 범위 조정
  
  • peopleProcessed >= n: mid 시간이 충분히 길어 n명을 처리할 수 있는 경우, 더 작은 시간에서 조건을 만족하는지 확인합니다.
  • peopleProcessed < n: mid 시간이 부족하므로 시간을 늘려야 합니다.