[프로그래머스] 입국심사 - 자바 풀이

이 문제는 이분 탐색(Binary Search) 을 이용해서 해결할 수 있는 전형적인 최적화 문제입니다.
전체적인 아이디어는 다음과 같습니다.

---

✅ 문제 요약

• n명의 사람이 입국심사를 기다림
• 각 심사관이 한 사람을 처리하는 시간은 times 배열에 있음
• 모든 사람이 심사를 받는 데 걸리는 최소 시간을 구하기

---

💡 핵심 아이디어

어떤 시간 t가 주어졌을 때, 그 시간 내에 n명을 처리할 수 있는지를 판단할 수 있다면,
t를 이분 탐색으로 줄여가며 최소의 시간을 구할 수 있습니다.

만약 28분이라는 시간이 있다고 치면?

각 심사관이 28분 안에 몇 명 처리할 수 있을까요?

• 28 / 7 = 4명 (첫 번째 심사관)
• 28 / 10 = 2명 (두 번째 심사관)
• 총 6명 처리 가능

근데 더 짧은 시간에도 가능할 수도 있잖아요?

---

🔍 여기서 이분탐색이 들어가는 이유!

"정답이 될 수 있는 시간"은 1분 ~ (가장 느린 심사관 × n) 사이에 있습니다.

즉, 1분부터 최대 시간까지의 범위에서, 최소 시간을 찾는 탐색을 하고, 각 시간(mid)에 대해, 그 시간 동안 n명을 처리할 수 있냐? 를 조건으로 판단하는 것입니다!

 

요소	설명
탐색 범위	1분부터 max(times) * n분까지
mid	우리가 현재 검사해보는 "후보 시간"
조건	mid 시간 동안 처리 가능한 인원이 n명 이상인지?
조건 만족	답이 될 수 있으니 mid보다 더 작은 시간도 검사 (오른쪽 줄임)
조건 불만족	시간이 부족하니까 더 많은 시간 필요 (왼쪽 늘림)

---

✔️ 알고리즘 단계

1. 이분 탐색 범위 설정
   • 최소 시간 start = 1
   • 최대 시간 end = 가장 느린 심사관 시간 × n
     (가장 느린 심사관이 전부를 처리하는 경우)
2. 이분 탐색 진행
   • 중간 시간 mid를 기준으로 모든 심사관이 mid 분 동안 처리할 수 있는 사람 수를 계산
   • 이 수가 n보다 크거나 같다면, 가능한 시간이므로 더 작은 시간도 가능할 수 있으므로 end = mid - 1
   • 부족하면 start = mid + 1
3. 이분 탐색이 끝나면 최소 시간이 start에 저장됨

---

✅ Java 코드

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;

            long total = 0;
            for (int time : times) {
                total += mid / time; // 각 심사관이 mid 시간 동안 처리 가능한 인원 수
            }

            if (total >= n) {
                answer = mid; // 가능한 시간
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return answer;
    }
}

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!