👀 문제
https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=kotlin
👊 도전
1. 설계
- 문제 조건에 맞게 진행
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
fun solution(n: Int, times: IntArray): Long {
times.sort()
var answer: Long = 0
var left: Long = times.first().toLong()
var right: Long = n * times.last().toLong()
while (left <= right) {
val mid = (left + right) / 2 // 임의의 시간 설정 (mid분 동안 심사 가능한 사람 수를 체크하기 위함)
var sum: Long = 0
times.forEach { time ->
sum += mid / time // mid분 동안 심사관들이 처리할 수 있는 사람 수
}
if (sum >= n) {
answer = mid
right = mid -1
} else {
left = mid + 1
}
}
return answer
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 이분탐색을 이용한다
- 이분탐색을 하기 위해서는 배열이 오름차순으로 정렬되어야 한다.
- left는 times의 최솟값(짧은 심사관으로 끝나는 케이스), right는 최댓값이다.
- mid는 times 범위 내 임의의 시간으로, 이분탐색을 통해 left와 right의 중간점으로 한다. mid내에 n명을 처리할 수 있다면 answer이 될 수 있다.
- mid시간 내 심사 가능한 사람 수를 찾는다
- times의 원소를 하나씩 꺼내서 mid분 안에 심사관이 몇 명을 소화할 수 있는지(time) 계산한다.
- 총합 sum(mid내 가능한 사람 수)이 n보다 크다면 answer이 될 수 있으므로 answer을 갱신하고, 이게 최솟값인지는 알 수 없으므로 범위를 줄여 다시 체크한다.