[99클럽 5기 코테 스터디 TIL 보너스문제] 입국심사 (feat. 이분탐색)

1) 문제

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

프로그래머스

 

클럽장 동찬님의 설명.. 굿!!

https://dong-chan.com/99club/java-bonus-dayone/

99클럽 타임어택 보너스 문제풀이 [입국심사]

 

 

2) 풀이

 

• 입력 값 처리
  • times 배열은 심사관들이 한 명을 처리하는 데 걸리는 시간을 나타냄
  • 배열을 정렬하여 가장 빠른 심사 시간부터 접근함
• 이분 탐색 설정
  • 최소 시간 left는 1분으로 시작
  • 최대 시간 right는 가장 느린 심사관이 모든 사람을 처리하는 경우로 설정
  • right=times[times.length - 1]×n
• 이분 탐색 수행
  • mid는 현재 탐색 중인 시간
  • mid 시간 동안 각 심사관이 처리할 수 있는 사람 수를 계산하여 sum에 더함
  • sum >= n인 경우, 더 적은 시간에서도 가능할지 확인하기 위해 right = mid - 1로 줄임
  • 그렇지 않다면, 시간을 늘려야 하므로 left = mid + 1로 설정
• 결과 반환
  • 모든 사람이 심사를 받는 데 필요한 최소 시간을 answer에 저장하고 반환

 

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] 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 시간 내에 처리할 수 있는 사람의 수 계산
            long sum = 0;
            for (int time : times) {
                sum += mid / time;
                if (sum >= n) break; // 필요한 사람 수를 초과하면 더 계산하지 않음
            }

            // 모든 사람을 처리할 수 있는 경우
            if (sum >= n) {
                answer = mid; // 최솟값 갱신
                right = mid - 1; // 시간을 줄여본다
            } else {
                left = mid + 1; // 시간을 늘려본다
            }
        }

        return answer;
    }
}