[프로그래머스] 알고리즘 79일차 : 예산

 

programmers.co.kr/learn/courses/30/lessons/12982

코딩테스트 연습 - 예산

C++ 그리디 알고리즘

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

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

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

 

접근방법

처음 문제 읽을 때 0-1 knapsack 같다는 생각이 들었다. 근데 값어치와 무게가 있는게 아니라 아주 간단한 그리디 문제인 것 같다.

많은 부서를 지원하는게 목표라 냅색으로 치면 그냥 적은 무게 순으로 많은 물건을 담으면 되는 문제이다.

오름차순으로 정렬해서 꽉 찰때까지 담으면 된다.

 

*

코드를 수정하다보니 세가지 정도의 풀이가 나왔다. 첫번째 풀이는 그냥 빠르게 풀어봤고(9분 소요)

두번째 풀이는 내가 생각했을 때 더 효율적인 코드로 바꿨다. (for문 대신 while문으로 풀이. 조건문이 줄었다. (4분소요)

세번째 풀이는 다른 사람의 코드를 보고 고쳐풀었다. sum변수에 지원금액을 저장해서 예산과 비교하는 방법 대신

예산에서 지원 금액을 빼는 것이다. 그럼 sum 변수를 사용하지 않아도 된다. (4분소요)

(풀이 시간 : 9분, 4분, 4분)

 

오답노트

두번째 풀이에서 모두 담아도 남는경우 cnt <= d.size() 를 처리해 주지 않아서 틀렸었다.

 

소스코드

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

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0;
    sort(d.begin(), d.end());
    int sum = 0;
    int cnt = 0;
    while(sum <= budget && cnt <= d.size()){
    	sum+= d[cnt++];
    }
    answer = cnt-1;
    return answer;
}

두번째 풀이

 

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

using namespace std;

int solution(vector<int> d, int budget) {
    int answer = 0;
    sort(d.begin(), d.end());
    int cnt = 0;
    while(budget>=0 && cnt <= d.size()){
        budget-=d[cnt++];
    }
    answer = cnt-1;
    return answer;
}

세번째 풀이

 

백준 풀때는 아무리커도 배열쓰는 경우가 많았는데

프로그래머스는 입력값을 벡터로 줘서 확실히 벡터 사용에 익숙해졌다.

사실 벡터가 더 효율적이라 벡터를 쓰는게 유리한데 이번에 익숙해져서 좋다.

 

스위프트 풀이

import Foundation

func solution(_ d:[Int], _ budget:Int) -> Int {
    var varBudget: Int = budget
    var deptCnt: Int = 0
    var costs: [Int] = d.sorted()
    
    while deptCnt < d.count && varBudget - costs[deptCnt] >= 0 {
        varBudget -= costs[deptCnt]
        deptCnt += 1
    }
    
    return deptCnt
}

import Foundation

func solution(_ d:[Int], _ budget:Int) -> Int {
    var sumOfCost: Int = 0
    var deptCnt: Int = 0
    let costs = d.sorted()
    
    for cost in costs {
        let preSumOfCost: Int = sumOfCost + cost
        if preSumOfCost <= budget {
            sumOfCost = preSumOfCost
            deptCnt += 1
        } 
        else { break }
    }
    
    return deptCnt
}

코드 길이 + 변수를 사용하지 않아도 된다는 점에서 1 코드가 더 효율적이지만

클린코드를 읽고 있는 입장에서 변수명으로 의미를 표현하는게 읽기쉬운 코드라고 생각해서

2번코드가 더 명확한 것 같다. 하지만 로직 자체가 달라지는거니까 1번이 더 좋을수도