[프로그래머스] 예산

1. 문제 설명

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

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

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

 

- 제한 사항

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

2. 풀이 코드

#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;


int partition(vector<int>& arr, int low, int high)
{
    int pivot = arr[high];
    int i = low-1;
    
    for(int j=low ; j<high; j++)
    {
        if(arr[j]< pivot)
        {
            swap(arr[++i], arr[j]);
        }
    }
    
    swap(arr[i+1],arr[high]);
    
    return i+1;
}


void quickSort(vector<int>& arr, int low, int high)
{
    if(low<high)
    {
        int pivotIdx = partition(arr, low, high);
        quickSort(arr, low, pivotIdx-1);
        quickSort(arr, pivotIdx+1, high);
    }
    
    
}



int solution(vector<int> d, int budget) {
    int cnt = 0;
    int dSize = d.size();
    quickSort(d, 0, dSize-1);
    
    for(int i = 0; i<dSize; i++)
    {
        budget-= d[i];
        if (budget < 0)
            break;
        cnt++;
    }
    
    return cnt;
}

 

3. 정리

적은 예산인 부서부터 지원하면 최대한 많은 부서들을 지원할 수 있다.

배열을 오름차순으로 정렬 후 반복문을 통해 예산이 음수가 되기 전까지 카운팅한다.

 

단계	시간복잡도
정렬 (퀵정렬)	O(N log N) (평균), O(N²) (최악)
for 루프 (탐색)	O(N)

 

 

전체 시간 복잡도는 평균적으로 O(N log N + N) = O(N log N) , 최악의 경우 O(N² + N) = O(N²) 이다.

 

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