[Python] 프로그래머스. 예산 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산 | 프로그래머스

 

이 문제를 처음 접했을 때에는 이분탐색을 쓰지 않아도 해결할 수 있었다. budget 최댓값에서 1씩 줄여가며 조건에 맞을 때까지 계산하면 효율성도 통과가 됐었던 걸로 기억한다.

 

오랜만에 다시 들어가보니 테스트케이스가 바뀌었다고 해서 이분탐색으로 풀었다.

 

 

 

	def solution(budgets, M):
	mins, maxs = 0, max(budgets)
	answer = 0
	while mins <= maxs:
	mid = (mins + maxs) // 2
	temp = [i if i < mid else mid for i in budgets]
	if sum(temp) > M:
	maxs = mid - 1
	elif sum(temp) <= M:
	answer = mid
	mins = mid + 1
	return answer

view raw [프로그래머스] 예산.py hosted with ❤ by GitHub