[프로그래머스][PYTHON] Lv. 1 예산

문제 설명

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

프로그래머스

 

문제를 보고 처음 든 생각이 그리디 알고리즘 문제라는 것이였다!

그리디 알고리즘은 현재 상황에서 당장 좋은 것만 고르는 방법이다. 

 

내 풀이

최대한 많은 부서를 지원해줘야 하기 때문에,

작은 예산을 가진 팀들부터 차례대로 지원해서 최대한 많은 부서를 찾으면 된다. 

즉, 주어진 d 배열을 오름차순 정렬한 뒤, 

각 값을 차례대로 더해, 이 값이 전체 예산보다 작으면 answer을 더하는 식으로 진행하였다. 

# 그리디 알고리즘 -> 가장 좋은 것 고르기!
def solution(d, budget):
    answer = 0
    tmp = 0
    # 주어진 금액을 정렬하여, 작은 값부터 차례대로 더함
    for i in sorted(d):
        tmp += i
        # 더한 값이 예산보다 작으면 answer += 1
        if tmp <= budget:
            answer += 1
        else:
            break
    return answer

 

 

다른 사람 풀이

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

 

이 풀이는 먼저 d 배열을 정렬하고, 

d 배열의 합이 예산(budget)보다 작아질 때까지 마지막 원소를 pop 해주는 방식이다. 

그 후, 남은 d 원소의 개수를 구하는 방식이다. 

생각치도 못한 방법이었다...!

 

느낀점

뭔가 내가 제대로 풀어도, 잘 풀었는지 아닌지 잘 모르겠다!!!!!!!!!!!1

답만 맞으면 되는건가..hmm.....