99클럽 코테 스터디 3일차 TIL + 이분탐색

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

def solution(n, times):
    answer = 0
    
    left = min(times)
    right = max(times) * n # 가장 오래걸릴 수 있는 경우
    
    while left <= right:
        mid = (left + right) // 2
        checked = 0
        
        for t in times:
            checked += mid // t # mid 시간 동안 t시간으로 심사 가능한 인원
            
        if checked >= n: # mid 시간 동안 심사 받은 인원이 n명이 넘으면 시간을 더 줄여도 됨
            right = mid - 1
            answer = mid
        else:
            left = mid + 1
    return answer

• 제한사항을 보고 이분탐색 으로 풀면 될 것 같다는 유추를 했지만, n과 times[]를 고려해야 해서 어렵게 생각했던 것 같다.
• 구해야 하는 값은 모든 사람이 심사를 받는데 걸리는 시간의 최솟값 이기 때문에 left, right를 각각 times의 최솟값, times의 최댓값 * n 으로 초기 설정함
• 찾고자 하는 시간 mid 시간 동안 심사 받는 인원을 체크하는 변수 checked 로 mid 시간 동안 t시간으로 심사 가능한 인원의 합을 구함
• 이때 checked가 심사를 기다리는 인원인 n명보다 크다면 심사 받는 시간인 mid를 줄여도 되기 때문에 right = mid - 1로 설정, 그렇지 않다면 더 큰 값을 기준으로 해야 하기 때문에 left = mid + 1로 설정

 

• for문 안에서 checked가 n 이상이 되면 더이상 확인할 필요가 없기 때문에 for문 안에 조건문을 추가해주면 더 좋을 것 같다.

for t in times:
	checked += mid // t # mid 시간 동안 t시간으로 심사 가능한 인원
    if checked >= n:
    	break