탐욕법 활용 기초편

1. 문제

 

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

코딩테스트 연습 - 예산

 

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다.

 

그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다.

 

그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다

 

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다.

 

예를 들어 1000원을 신청한 부서에는 정확히 1000원을 지원해야 하며, 1000원보다 적은 금액을 지원해 줄 수는 없습니다

 

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget가 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return하도록 solution 함수를 완성하세요

 

 

2. 제한사항

 

d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.

 

d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100000이하의 자연수입니다

 

budget는 예산을 나타내며, 1 이상 10000000이하의 자연수입니다

 

 

3. 입출력 예시

 

그림1. 입출력 예시

 

4. 나의 풀이

 

최댓값이나 최솟값 구하라하면 탐욕법을 생각하는게 맞는것 같다

 

부서의 최대 수를 구하라고 했으니까 최대 상황부터 시작해서 검사를 해서 아니면 하나씩 빼나가는거지

 

def solution(d, budget):

    answer = 0
    
    if sum(d) <= budget:
        
        return len(d)
    
    else:
        
        while len(d) != 0:
            
            if budget >= max(d):
                
                budget = budget - d.pop(d.index(min(d)))
                
                answer += 1
            
            else:
                
                d.pop(d.index(max(d)))
                
    
    return answer

 

그래서 처음부터 sum(d)가 budget과 맞는지 안맞는지 검사하고 맞으면 바로 len(d)를 return하면 돼

 

answer = 0
    
    if sum(d) <= budget:
        
        return len(d)

 

근데 여기서 문제를 잘 봐야하는데 budget과 딱 맞게 지원을 해줘야하느냐? 지원을 해주고 budget이 남아도 되는것인가?

 

입출력 예시에 답이 나와있더라고.. budget이 남아도 된다

 

그래서 초기에 sum(d)가 budget보다 작더라도 전부다 지원하고 budget이 남아도 상관없기 때문에

 

sum(d) <= budget이면 모든 부서에 다 지원해줄 수 있으므로 len(d)를 return

 

다음으로 생각을 해봐 sum(d)가 budget보다 크다면….

 

d에서 min값을 차례대로 더해나가면 그 합이 최소니까 최대한 많이 지원을 해줄 수 있을거임

 

가장 적게 돈을 신청한 부서부터 지원을 한다면 가장 많이 지원을 해줄 수 있을거다

 

이것이 바로 탐욕법

 

else:
        
        while len(d) != 0:
            
            if budget >= max(d):
                
                budget = budget - d.pop(d.index(min(d)))
                
                answer += 1
            
            else:
                
                d.pop(d.index(max(d)))
                
    
    return answer

 

budget이 max(d)보다 크거나 같다면… budget에 min(d)를 빼나간다

 

min(d)를 한번 빼는 순간 1명에 지원을 해주는거니까 answer에 1을 더한다

 

budget이 줄어들테니까 어느 순간부터는 budget이 max(d)보다 작아질거임

 

그러면 max(d)에는 더 이상 지원해줄 수 없으므로 max(d)를 d에서 제거함

 

이런 경우에는 지원을 해준 것이 아니니까 answer에 1을 더하지 않는다

 

이 과정을 계속 반복한다면 매 순간 min(d)를 지원해주는것이고 지원할 수 없는 부서는 제거되니까 d의 길이가 0이 되는 순간 반복문을 탈출하고 최종 answer를 return

 

 

5. 다른 풀이

 

def solution(d, budget):
    
    d.sort()
    
    total = sum(d)
    
    while budget < total:
        
        total = total - d.pop()
        
    return len(d)

 

나는 budget에서 min값을 빼나갔는데 반대로 max값을 d에서 빼나갈수도 있을거임

 

핵심 아이디어는 최솟값들을 더해나가야 최대한 많은 부서에 지원할 수 있다는것

 

d.sort()를 통해 오름차순으로 정렬하고

 

total = sum(d)를 해서 미리 sum을 한다

 

----------------------------------------------------------------------------------------------------------------------------

sort()를 왜 하는가??    (반드시 기억해야함 매우 중요)

 

나는 d.index(min(d))를 통해 min(d)의 index를 찾고 이 index를 지정하여 d.pop(index)해서 min을 빼나가는 비효율적인 과정을 거쳤는데

 

정렬을 하고나면 d.pop()을 통해 손쉽게 max값을 빼나갈 수 있다

----------------------------------------------------------------------------------------------------------------------------

 

budget이 total보다 크거나 같으면 d에 존재하는 부서들을 모두 지원을 할 수 있는거니까

 

budget가 d의 합인 total보다 작다면 d의 최댓값을 빼는게 최대한 많은 부서를 지원할 수 있을거임

 

while 반복문을 통해 budget<total이면 반복을 수행하고 정렬을 했기 때문에 d.pop()은 맨 오른쪽 값인 최댓값을 뺀다

 

어느 순간부터 budget이 d의 합보다 커지는 순간이 있는데 그 순간 while문을 탈출하고 d의 길이를 구하면…

 

최솟값부터 더해나가는거니까 최대한 많은 부서를 지원한거임

 

def solution(d,budget):
    
    d.sort()
    
    while budget < sum(d):
        d.pop()
    
    return len(d)

 

위와 같이 할 수도 있지만 while 반복문 돌때마다 sum(d)를 통해 O(N)의 과정을 수행해야해서 비효율적일 수 있다고함

 

이렇게 섬세하게 생각을 하는 코딩이 필수

 

6. 되돌아보기

 

탐욕법을 생각한건 확실히 좋았고 

 

최솟값을 더해나갈지 최댓값을 빼나갈지.. 핵심도 나름 잘 파악했지만

 

문제를 정확히 이해하지못해 헤맨게 조금 아쉽다

 

budget이 남아도 되는것인가? budget이 딱 맞아야하는것인가?

 

입출력 예시나 제한사항 같은 것들이 하나의 힌트가 될 수 있다는 것도 기억하면 좋고

 

다른 풀이 보니까 핵심은 잘 파악했지만… 확실히 고수의 길은 멀다..

 

정렬을 미리 해놓으면 d.index(min(d))를 통해 비효율적으로 min을 찾는게 아니라 d.pop(0)를 하면 바로 최솟값을 뺄 수 있다는거

 

매 순간 list의 합을 구할 것이냐… 미리 구해놓고 빼나갈것이냐… 효율적인 생각을 할 수 있는것도 중요하니까 체크