[프로그래머스] 프로그래머스 Level1 예산 C++

문제

https://programmers.co.kr/learn/courses/30/lessons/12982?language=java 

코딩테스트 연습 - 예산

풀이

그리디 유형의 문제이고, 처음에 자바로 백트래킹으로 접근했다가 테스트케이스는 통과하지만 시간초과가 났었다. 최종적으로 문제 해결은 C++로 진행하였다.

우선 최대한 많은 부서들의 물품을 구매하는 것이 정답이기에 부서별 신청 금액인 d를 오름차순 정렬해주었다. 오름차순 정렬을 통해 신청 금액이 낮은 부서부터 차례대로 값을 끼워넣어 최대한 많은 부서의 물품을 구매할 수 있도록 해주었다.

정렬해준 이후가 가장 중요한데 낮은 금액부터 차례대로 더하다가 예산과 같은 값이 되면 그게 곧 정답이므로 멈추어 주었고, 그게 아니라 예산을 초과하게 되면 예산을 빼주어 없던 일로 만들어버리면 정답을 구할 수 있다. 

 

코드

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

using namespace std;

int solution(vector<int> d, int budget) {
    
    int answer = 0;
    int cost = 0;

    sort(d.begin(), d.end());

    for (int i = 0; i < d.size(); i++) 
    {
        cost += d[i];
        answer++;
        if (cost == budget)
        {
            break;
        }
        else if (cost > budget)
        {
            cost -= d[i];
            answer--;
        }
    }


    return answer;
}

시간 초과 코드(백트래킹 - JAVA)

import java.util.Arrays;
import java.util.Collections;

class Solution {

    int result = 0;
    boolean flag = false;
    boolean[] isused = new boolean[101];
    int[] arr = new int[101];

    public int solution(int[] d, int budget) {

        int answer = 0;

        reverseSort(d);

        for(int i = d.length; i > 0; i--) {
            func(0,0, i, d, budget);
        }

        answer = result;

        return answer;
    }

    public void func(int idx, int cnt, int m, int[] d, int budget) {

        if(cnt == m) {
            int temp = 0;
            for(int i = 0; i < m; i++) {
                temp += arr[i];
            }
            if(temp == budget) {
                result = m;
                flag = true;
                return;
            }
            return;
        }

        if(flag == false) {
            for(int i = idx; i < d.length; i++) {
                if(!isused[i]) {
                    isused[i] = true;
                    arr[cnt] = d[i];
                    func(i + 1, cnt + 1, m, d, budget);
                    isused[i] = false;
                }
            }
        }
    }

    public void reverseSort(int[] arr) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length / 2; i++) {
            int temp = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = temp;
        }
    }
}