루나의 TIL 기술 블로그

프로그래머스 level 1 예산

01 Jul 2021 | 기초 프로그래머스 TIL

걸린 시간 : 1시간

문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

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

입출력 예

d budget result
[1,3,2,5,4] 9 3
[2,2,3,3] 10 4

사고과정

예산신청 리스트를 정렬해서 작은 수부터 더해준다.
더한 값이 예산보다 커질때까지 더해주고 카운트를 출력한다.

def solution(d, budget):
    d.sort()
    count = 0
    sum = 0
    while sum < budget:
        for i in d:
            sum += i
            count += 1
    return count

이렇게 하면 [1,3,2,5,4], 9가 입력되었을 때 3이 나와야하는데 5가 나온다. sum을 for문 안에서 돌린 결과가 바깥의 while문에 적용되기를 바라는 것은 말이 안 되는 것 같다.

def solution(d, budget):
    d.sort()
    count = 0
    sum = 0
    for i in d:
        count += 1
        sum += i
        if sum == budget:
            return count
        if sum > budget:
            return count-1
        if sum < budget:
            if count == len(d):
                return count

코드를 이렇게 수정했는데 이번에는 테스트케이스 2,6,18,19번이 실패한다.
질문하기를 봤더니 부서가 하나인 경우도 생각해야한다고 한다.
juu님의 코드에 따라 아래 부분을 보충했다.

제출답안

def solution(d, budget):
    d.sort()
    count = 0
    sum = 0
    for i in d:
        count += 1
        sum += i
        if sum == budget:
            return count
        if sum > budget:
            return count-1
        if sum < budget:
            if count == len(d):
                return count

뭔가 개선의 여지가 많이 보이는 코드같다.

모범 답안

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

깔끔하고 좋은 코드라고 생각하는데 댓글에서는 sum()이 반복되어 시간 복잡도가 O(n^2)가 되니 매번 원소 값을 하나씩 빼는 편(O(n))이 낫겠다고 한다.

주요 포인트 및 생각해볼 점

시간복잡도 설명을 두번쯤 들은 것 같은데 실제로 적용해보기는 쉽지 않다.

Related Posts