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

(주)그렙

[programmers] 프로그래머스 예산 Level 3

(Python)

(글쓴날 : 2020.06.07)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 예산 Level 3

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

국가 예산의 총액과 지방의 예산 요청 리스트가 주어질 때, 전체 국가예산 이하에서 가능한 최대의 지방 예산 상한액을 구하는 문제입니다.

 

저의 경우, 이분 탐색을 적용하였고, Python을 사용했습니다.

지방의 예산 요청 리스트에서 가장 큰 금액을 right로 잡고 이분 탐색하였고, 문제에서 정의한 규칙에 상응하는 값 중 최대 상한액을 구하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

def solution(budgets, M):
    answer = 0
    
    left = 0
    right = max(budgets)
    
    while(left <= right):
        mid = (left + right) // 2
        
        isPossible = True
        dividend = 0
        for b in budgets:
            if b <= mid:
                dividend += b
            else:
                dividend += mid
                
        if dividend > M:
            isPossible = False
        
        if isPossible:
            answer = mid
            left = mid + 1
            continue
            
        right = mid -1
             
    return answer

---