[Lv.1] 예산 [프로그래머스_코딩테스트] [Greedy, 정렬] [25분]

🔍 문제 요약

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

프로그래머스

예산 금액인 budget이 주어지고 d 배열에 각 부서에서 신청한 금액을 정렬되지 않은 채로 전달받았을 때 최대 몇개의 부서에 지원을 할 수 있는지 계산 문제.

 

🧠 나의 접근 방식과 시행착오

문제 푼 시간이 지금까지 봤던 문제들 중에 제일 빨랐던 10분. 해당 문제는 한정된 수치로 최대 몇개를 만들 수 있는지 얻어오는 문제로 작은 수부터 큰 숫자로 올림차순 정렬을 시키고 예산에서 빼면서 count를 증가시키면 된다. 문제의 길이에 비해서 오히려 너무 간단한 문제였던 것 같은 느낌..

using System;

public class Solution
{
    /// <summary>
    /// 예산
    /// https://school.programmers.co.kr/learn/courses/30/lessons/12982
    /// </summary>
    public int solution(int[] d, int budget)
    {
        int count = 0;
        
        // d : 부서별 신청 금액
        // budget : 예산
        // 최대한 많은 신청금액 지원
        // 문제 핵심 : 작은 신청금액부터 지원해주면 최대 개수가 나옴
        
        // 오름차순 정렬
        Array.Sort(d);

        for (int i = 0; i < d.Length; i++)
        {
            if (budget >= d[i])
            {
                count++;
                budget -= d[i];
            }
            else
            {
                break;
            }
        }
        
        return count;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        var d1 = new int [] {1,3, 2, 5, 4};
        var d2 = new int [] {2,2, 3, 3};
        int budget1 = 9;
        int budget2 = 10;
        
        Console.WriteLine(sl.solution(d1, budget1));
        Console.WriteLine(sl.solution(d2, budget2));
    }
}

✅ 풀이 코드

이번에는 풀이코드가 따로 없다. 시도했던 코드에서 고칠 것이 따로 없어 보여서 따로 적을 내용이 없긴 하다.

🔄 정리

한정된 숫자에서 최대 n개의 수를 만들어내는 문제의 접근 방식에 대해서 확실히 방향성이 잡히는 듯 하다. 일단 작은 것부터 우선해서 빼면서 n개를 찾는 것.