정재영

1일 1문제 푸는 중

문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.
물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.
부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

  • d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
  • d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
  • budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.
  • 문제 보러가기


문제 풀이

(1) Pseudo-Code

  • 부서별로 신청한 금액의 총합이 전체 예산 이하인 경우 모든 부서에 금액을 지원할 수 있도록 한다(부서의 길이 출력).
  • 부서별로 신청한 금액을 오름차순 정렬하고 금액이 큰 것을 하나씩 빼면서 예산금액을 맞출 수 있는지 확인한다.
  • 부서를 하나씩 빼면서 신청금액의 총 합이 예산 금액 이하가 되면 그때의 부서 개수를 출력하도록 한다.

(2) 코드 작성

def solution(d, budget):
    sorted_d = sorted(d)
    # 모든 부서에 금액일 지원할 수 있는 경우
    if sum(sorted_d) <= budget:
        return len(sorted_d)
    # 예산 범위 내에서 지원할 수 있는 부서의 개수를 찾아야하는 경우
    for i in range(len(sorted_d)):
        if sum(sorted_d[:-1-i]) <= budget:
            return len(sorted_d) - i - 1

(3) 코드 리뷰

처음에 while 문을 사용하여 코드를 작성해 보았는데 테스트 7 ~ 테스트 17 에서 실패(시간초과) sign이 떴다. 실패 코드는 아래와 같다. 우선 문제 접근 방법은 부서가 신청한 금액의 총 합이 예산금액 내에 있으면 그대로 출력한다. 그리고 전체 부서의 개수에서 그룹을 만들어가는데 그룹을 만들 때 부서의 크기는 원래 길이에서 하나씩 빼가며 combinations 함수로 부서 내 신청금액이 담긴 배열을 만들었다. 그리고 그 그룹들의 최솟값이 예산금액 내에 위치한다면 반복문을 멈추고 예산 금액 내에서 신청할 수 있는 최대의 부서 크기를 출력하도록 작성했다. 하지만 반복문(while) + 조합(combination) 의 사용으로 인해 연산 비용이 많이 발생하여 코드 실패가 뜬 것같다. 주어진 데이터의 크기를 고려하여 반복문이나 조합 등이 사용될 때 연산비용이 많이 들 것으로 예상되는 경우에선 그 방법을 대신할 수 있는 방향을 찾도록 노력해 보아야겠다.

🔥 실패코드 공유

# 실패 코드: 테스트 7 ~ 17에서 시간초과
from itertools import combinations

def solution(d, budget):
    if sum(d) <= budget:
        return len(d)
    
    group_num = len(d) - 1
    while group_num > 0:
        group_list = list(combinations(d, group_num))
        sum_group_list = [sum(g) for g in group_list]
        if min(sum_group_list) <= budget:
            break
        else:
            group_num -= 1
    return group_num

👩🏻‍💻개인 공부 기록용 블로그입니다
오류나 틀린 부분이 있을 경우 댓글 혹은 메일로 따끔하게 지적해주시면 감사하겠습니다.

댓글남기기