1. 문제
https://school.programmers.co.kr/learn/courses/30/lessons/43238
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
2. 풀이과정
이분 탐색 문제인 걸 알면서 풀었는데도, 아이디어가 잘 떠오르지 않은 문제였다.
이분 탐색 문제를 많이 풀어봐야겠다..!
사람수 n명이 주어지고, 입국심사관이 한 명을 심사하는데 걸리는 시간이 times 배열로 주어진다.
모든 사람들이 입국심사를 가장 빨리 끝내는 시간을 구하는 문제이다.
문제접근
이 문제는 최악의 경우 n = 1,000,000,000 이고, 각 심사관이 한명을 검사하는 시간이 1,000,000,000 이다.
또한, 심사관은 최대 100,000명이 될 수 있다. => 시간 초과에 유의해야 한다.
이분탐색으로 접근해서 풀어야 시간 초과가 발생하지 않으면서 문제를 해결할 수 있다.
- times 배열 오름차순 정렬
- 이분 탐색 범위 지정
- left = 0(최소 시간)
- right = 최대 시간 x 사람 수(최대 시간)
- 이분 탐색 시작(right >= left)
- mid(제한된 시간) 구한다
- times를 돌면서 mid(제환된 시간)에서 times[i] 로 나눈 몫을 count에 누적한다. => 제한된 시간동안 몇 명을 처리할 수 있는지 계산
- count >= n이면, 제한된 시간에 모든 사람이 검사받을 수 있다.
- 제한된 시간 answer에 저장(정답 후보)
- 최솟값을 구하기 더 짧은 시간을 탐색(right = mid - 1)
- count < n이면, 제한된 시간안에 모든 사람이 검사받을 수 없다.
- 더 긴 시간이 필요(left = mid + 1)
- answer(결과) 반환
3. 코드
class Solution {
public long solution(int n, int[] times) {
Arrays.sort(times);
long left = 0;
long right = times[times.length - 1] * (long) n;
long answer = 0;
while (right >= left) {
long mid = (left + right) / 2;
long count = 0;
for(int i = 0; i < times.length; i++) {
count += (mid / times[i]);
}
if(count >= n) {
answer = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return answer;
}
}
'Algorithm' 카테고리의 다른 글
| [백준] 3190. 뱀 -JAVA (0) | 2025.09.14 |
|---|---|
| [백준] 2178. 미로탐색 - JAVA (0) | 2025.09.10 |
| [백준] 3273. 두 수의 합 - JAVA (0) | 2025.09.02 |
| [백준] 2346. 풍선 터뜨리기 (0) | 2025.08.29 |
| [Programmers] 2019 KAKAO BLIND RECRUITMENT 후보키 - JAVA (1) | 2025.08.28 |