나의 풀이
def binarySearch(left, right, n, times):
answer = right
while left <= right :
mid = (left+right) // 2
cnt = 0
for t in times :
cnt += mid // t
if cnt >= n :
answer = min(answer, mid);
right = mid - 1
else :
left = mid + 1
return answer
def solution(n, times):
min_time = 0
max_time = max(times) * n
answer = binarySearch(min_time, max_time, n, times)
return answer
- 이분탐색은 탐색하는데 걸리는 시간이 O(log N) 이기 때문에, 탐색해야 하는 input 이 아주 큰 숫자일 때 사용하기 좋다.
- 따라서, 위 문제에서도 심사를 하는데 걸리는 시간을 기준으로 이분탐색 (1분 ~ 심사하는데 최대로 걸리는 심사위원의 시간 * N) 을 진행하였다.
- 시간을 조절하면서, 만약 해당 시간안에 N이라는 사람을 모두 심사할 수 있다면, answer 과 비교하여 더 작은 수라면 최소시간으로 갱신한다.
- mid = ( left + right ) // 2 라는 중간 시간을 정한 다음, mid 시간 안에 처리할 수 있는 사람의 수를 계산한다.
- for t in times :
cnt += mid // t
- for t in times :
- 이때 심사할 수 있는 사람 수(cnt) 가 심사해야되는 사람수(N) 보다 많으면 최소 시간을 잡기 위해 시간을 줄여본다.
- answer = min(answer, mid);
right = mid - 1
- answer = min(answer, mid);
- 만약, 심사할 수 있는 사람 수(cnt) 가 심사해야되는 사람수(N) 보다 적으면 시간을 늘여야 한다.
- left = mid + 1
'알고리즘 > 이분탐색' 카테고리의 다른 글
[백준] 1074번: Z - java (1) | 2023.02.20 |
---|---|
[프로그래머스] 가사 검색 - 파이썬(python) (0) | 2022.10.18 |
[백준] 2110번: 공유기 설치 - 파이썬(python) (0) | 2022.10.18 |
[프로그래머스] 징검다리 - 파이썬(python) (0) | 2022.09.24 |
댓글