[C#] 예산 - 프로그래머스

문제 : 부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 

 

제한사항 : 

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

 

풀이 : 삽질을 ...굉장히 많이한?...문제였다... 지문을 이해하지 못한게 제일 크다 처음 읽고서 배열을 의 원소를 사용해서 budget 에 가까운 값을 만드는 경우의 수를 만드는것이라고 이해해서.... 잘못 풀었다,.,,

결론은 주어진 buget 으로 얼마나 많은 부서를 지원할 수 있는 가였다... 즉 주어진 배열을 정렬 하고 차례로 빼나간다면

줄 수 있는 부서의 수가 정해지는것이었다... 젠장..

public static int solution(int[] d, int budget)
{
    int answer = 0;
    Array.Sort(d);
    foreach (var item in d)
    {
        if (item > budget)
        {
            break;
        }
        budget -= item;
        ++answer;
    }
    return answer;
}

 

잘못된 풀이... 삽질이 아깝다!ㅋㅋㅋㅋ 나름 생각한걸 구현 하게되서 일단 올려본다...

public static int solution(int[] d, int budget)
{
    int answer = 0;
    List<int> _list = new List<int>();
    Queue<List<int>> q = new Queue<List<int>>();
    int sumD = 0;

    for (int i = 0; i < d.Length; i++)
    {
        sumD = d[i];
        for (int j = i + 1; j < d.Length; j++)
        {
            if (sumD + d[j] <= budget)
            {
                sumD += d[j];
                _list.Add(d[j]);
                continue;
            }
        }
        _list.Add(d[i]);
        q.Enqueue(_list);
        _list = new List<int>();
    }
    answer = q.Dequeue().Count;
    for (int i = 0; i < q.Count; i++)
    {
        if (answer < q.Peek().Count)
        {
            answer = q.Dequeue().Count;
        }
    }
    return answer;
}