👀 문제
https://programmers.co.kr/learn/courses/30/lessons/43238
👊 도전
1. 설계
- 심사관들에게 주어지는 시간을 이분탐색으로 찾는다.
- 어떤 시간이 주어졌을 때, 심사관들이 몇 명을 심사할 수 있는지 계산하여 n보다 크면 시간을 줄이고, n보다 작으면 시간을 늘린다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
/**
*
* @author HEESOO
*
*/
class Solution {
public long solution(int n, int[] times) {
Arrays.sort(times);
long min=1;//최적의 경우 1초로 초기화
long max=(long)times[times.length-1]*n;//최악의 경우로 초기화
long mid=0;
long sum;
long answer = max;
while(min<=max){
sum=0;
mid=(min+max)/2;
for(int time:times){
sum+=mid/time;//심사관 당 맡을 수 있는 입국자 수
}
if(sum>=n){//더 맡을 수 있으므로 시간 줄임
if(mid<answer){
answer=mid;
}
max=mid-1;
}
else{//불가하므로 시간 늘림
min=mid+1;
}
}
return answer;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- long max의 초기화에서 (long)으로 형변환이 필요하다.
- 이것 때문에 테스트3,5,7,8에서 실패했다.
- 배열 times와 n은 모두 int형이고 두 곱이 int형을 초과할 수 있으므로 long 형변환이 필요하다.
- mid가 주어졌을 때, 심사관 당 맡을 수 있는 입국자 수를 계산한다.
- 심사관 당 맡을 수 있는 입국자 수=추정시간 값/심사관 당 심사시간.
- 모든 사람이 심사를 받는데 걸리는 시간을 mid라 할 때, mid당 심사위원들의 심사인원 수가 n보다 크다면 시간을 줄이고, 작다면 시간을 늘린다.
- 이때 mid안에 n명 심사가 가능하다면 answer과 mid 중 최솟값을 저장한다.
👏 해결 완료!
아직 이분탐색 문제의 유형을 잘 모르겠다. 언젠가는 감이 오겠지…?
참고
- [프로그래머스] 입국심사 https://greenapple16.tistory.com/49
- 프로그래머스_입국심사 https://woongsin94.tistory.com/185
- 이분탐색(binary search) https://webfirewood.tistory.com/108