[프로그래머스] 예산 (level 3) - 이분탐색/이진탐색 (python)

1. 문제 설명

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

 

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다. 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다.

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.
각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

 

---

2. 제한 사항

• 지방의 수는 3 이상 100,000 이하인 자연수입니다.
• 각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다.
• 총 예산은 지방의 수 이상 1,000,000,000 이하인 자연수입니다.

 

---

3. 입출력 예

budgets	M	return
[120, 110, 140, 150]	485	127

 

---

 

4. 나의 풀이

이 문제의 경우 '각 지방이 요구한 예산의 총합이 국가 예산보다 적은 경우, 지방 예산의 최댓값을 상한액으로 한다.' 라는 조건이 빠져 많은 사람들이 혼란에 빠졌던 문제이다. 따라서 반례에 대한 조건을 코드 초반에 달아주었다.

처음 문제를 접했을 때, 이분탐색이라는 카테고리를 보고 코드 어느 곳에 이분탐색을 써야할지 고민이 많았다. 우선 문제를 푸는게 우선이라 생각했고, (최대한 효율적인) 알고리즘을 고민해보았다.

 

이분탐색을 적용시키기 위해서는, 리스트가 정렬된 상태여야 한다. 인풋으로 받은 budgets을 정렬시킨 후, 반복문을 돌려 상한액을 갱신시켰다. 국가예산(M)을 지방 갯수(len(budgets))로 나누어 첫 상한액을 정하고 그 상한액이 정렬된 budgets에 들어가면 어느 위치에 들어가게 될지를 이분탐색을 이용하여 찾았다.

 

def binary(m_list, target):	#변형된 이분탐색
    left = 0 
    right = len(m_list) - 1

    while (left<=right):
        mid = (left+right)//2
        if m_list[mid] >= target: #중앙값보다는 작고
            if m_list[mid - 1] <= target: #그 직전보다 클때
                return mid #인덱스 리턴
            right = mid-1
        else :
            left = mid+1
    return 0 #자리를 찾지 못한 경우 맨앞에 배치

 

이분탐색의 경우 특정값을 리스트 내에서 '탐색'하는데 이용되기 때문에, 리스트에 들어있는 값을 인풋에 넣어야한다. 하지만 원하는 값의 위치를 찾아야하고 이 문제의 카테고리가 이분탐색이기 때문에 기존 이분탐색 함수를 약간 바꾸어 이용했다.

그 다음, budgets 에서 찾은 인덱스 이전의 것들은 모두 각 지방이 원하는 예산을 배정해줄 수 있기 때문에, 고려하지 않는다. 국가 총 예산에서 전액 지원 가능한 지방의 예산의 합을 빼서, 배정이 완료되지 않은 지방의 수로 나누어준다.

나누어준 값을 찾은 인덱스자리의 예산과 비교하여 예산이 더 큰 경우 답으로 return하고, 작은 경우 인덱스 이전의 값들을 제외하고 다시 찾기를 반복한다.

 

 

 

def solution(budgets, M):
    budgets.sort()
    if sum(budgets) <= M:
        return budgets[-1] # 모든 지방의 예산을 지원 가능할 때, 예산의 최댓값 == 상한액
    
    while(True):
        temp = M // len(budgets)
        idx = binary(budgets, temp)
        ceiling = (M - sum(budgets[:idx])) // (len(budgets) - idx)
        if budgets[idx] > ceiling:
            return  ceiling
        M -= sum(budgets[:idx])
        del budgets[:idx]
    return None

 

코드를 완성하고, 실행 및 제출 버튼을 눌렀을 때, while문에 return문을 제외하고 조건을 달지 않았기 때문에 무한루프에 빠지지 않을까 걱정했다. 하지만 다행히 테스트 9번 빼고 정확성과 효율성을 모두 통과할 수 있었다. 테스트 9번의 경우 binary search 함수를 돌릴때, target값이 budgets의 모든 값보다 작으면 인덱스 0을 return 해야 하는데 none을 리턴하게 만들어서 오류가 났다. 그 부분을 고치니 멀쩡하게 돌아가더라

 

항상 느끼지만, 문제풀때 알고리즘 카테고리를 알려주는게 좋을때도 있지만, 가끔은 답을 정해놓고 푸는 기분이라 더 헷갈리게 만든다 (솔루션은 많지만 출제자가 의도한 답을 하려고 노력하다보니??). 앞으로 코딩테스트 보러가면 문제만 보고 뚝딱뚝딱 풀어야하는데 그게 언제쯤 막힘없이 될지 걱정된다. 더더더더ㅓ 많이 연습해야지.

 

 

링크: https://programmers.co.kr/learn/courses/30/lessons/12982

 

코딩테스트 연습 - 예산