예산

1. 개요

프로그래머스
Lv.1
Summer/Winter Coding(~2018)
문제 바로가기

2. 문제 설명

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

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

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

2-1. 문제 설명 - 제한사항

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

2-2. 문제 설명 - 입출력 예

budget

result

[1,3,2,5,4]

[2,2,3,3]

2-3. 문세 설명 - 입출력 예 설명

입출력 예 #1 각 부서에서 [1원, 3원, 2원, 5원, 4원]만큼의 금액을 신청했습니다. 만약에, 1원, 2원, 4원을 신청한 부서의 물품을 구매해주면 예산 9원에서 7원이 소비되어 2원이 남습니다. 항상 정확히 신청한 금액만큼 지원해 줘야 하므로 남은 2원으로 나머지 부서를 지원해 주지 않습니다. 위 방법 외에 3개 부서를 지원해 줄 방법들은 다음과 같습니다.

1원, 2원, 3원을 신청한 부서의 물품을 구매해주려면 6원이 필요합니다.
1원, 2원, 5원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
1원, 3원, 4원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
1원, 3원, 5원을 신청한 부서의 물품을 구매해주려면 9원이 필요합니다.

3개 부서보다 더 많은 부서의 물품을 구매해 줄 수는 없으므로 최대 3개 부서의 물품을 구매해 줄 수 있습니다.

입출력 예 #2 모든 부서의 물품을 구매해주면 10원이 됩니다. 따라서 최대 4개 부서의 물품을 구매해 줄 수 있습니다.

3. 문제 해결

function solution(d, budget) {
  // 1) 현재의 부서 수와 신청 금액
  let answer = 0;
  let money = 0;

  // 2) 부서별 신청한 금액 오름차순
  d.sort((a, b) => a - b);

  for (let i = 0; i < d.length; i++) {
    // 3) 신청 금액이 예산 보다 클 경우 반복문 종료
    if (money + d[i] > budget) break;

    // 4) 부서수 +1
    answer += 1;

    // 5) 해당 부서의 신청 금액 추가하기
    money += d[i];
  }

  return answer;
}

1) 현재의 부서 수와 신청 금액

let answer = 0;
let money = 0;

문제에서 원하는 답은 최대 몇 개의 부서에게 신청 금액을 지원해줄 수 있는가?이다. 결국 지원가능 한 부서 수를 나타내는 변수 answer를 선언하였다.

또한 부서 별 신청 금액을 합한 금액이 예산보다 적어야 하기 때문에 신청 금액도 관리를 해야한다. 이를 위해 변수 money를 선언하였다.

2) 부서별 신청한 금액 오름차순

d.sort((a, b) => a - b);

배열 d에는 각 부서들이 신청한 금액이 들어있다. 가장 많은 부서를 지원해줄 수 있어야 하기 때문에 신청금액이 작은 것들 부터 정렬한다.

3) 신청 금액이 예산 보다 클 경우 반복문 종료

if (money + d[i] > budget) break;

현재까지 쌓인 신청 금액에 새로 들어온 신청 금액을 더했는데 예산을 초과하는 경우 그대로 반복문을 종료한다.

4) 부서수 +1

answer += 1;

3) 신청 금액이 예산 보다 클 경우 반복문 종료의 조건을 만족하지 하지 못한다면 아직 예산에는 여유가 있는 것이다. 그래서 지원할 수 있는 부서수에 1을 더한다.

5) 해당 부서의 신청 금액 추가하기

money += d[i];

지금까지 신청한 금액(money)도 항상 반복문에서 예산(budget)과 비교해야 하기 때문에 부서수(answer)가 1 만큼 오를 때 마다 해당 부서가 신청한 금액(d[i])도 기존 신청한 금액(money)에 더한다.

결과

4. Refactoring

function solution(d, budget) {
  let answer = 0;

  d.sort((a, b) => a - b).some((item) => {
    if (budget < item) return true;
    answer++;
    budget -= item;
  });

  return answer;
}

원래 풀이와 리팩토링 풀이는 얼추 비슷하지만 좀더 간단하게 표현을 해보았다.

먼저 메서드 체이닝을 통해 Array.sort()메서드와 Array.some()메서드를 실행하였다.
반복문도 for문이 아닌 Array.some()을 활용하였다. 이 메서드는 참인 값을 반환하게 되면 자동으로 반복문을 종료한다.
반복문의 안의 조건문도 수정하였다. money라는 변수를 넣어 지금까지의 신청 금액을 관리하는 것이 아니라 기존 예산에서 계속해서 신청 금액을 뺀다. 그러면 어느 순간 남은 예산이 새롭게 들어온 신청 금액보다 작을 경우가 생기는데 이 때 반복문을 종료한다.
```
if (budget < item) return true;
```
money 변수가 사라졌다. 그리고 아래와 같은 코드가 추가되었는데 이는 반복문이 실행 될 때 마다 남아있는 예산에서 계속해서 새롭게 들어온 신청 금액을 빼는 것이다.
```
budget -= item;
```

결과

실행 속도는 비슷하지만 원래의 풀이가 더 짧게 측정되는 경우가 더 많이 보인다. 하지만 개인적으로 가독성은 리팩토링을 마치고 난 후의 코드가 더 좋다고 생각한다.(사실 그거 마저 비슷해 보인다😂😂)

5. 다른 사람 풀이

여러 풀이가 있었다. 나와 같은 풀이가 가장 많이 보였고 정말 신기하게 한 줄로 풀이한 코드도 있었다. 하지만 나는 아래의 코드를 가져왔는데 그 이유는 내가 생각지 못한 메서드인 Array.reduce()를 사용하여 문제를 풀었고 코드 또한 지저분 하지 않아 보였기 때문이다. 해당 코드는 Alexsander Ham님의 코드이다.

function solution(d, budget) {
  return d
    .sort((a, b) => a - b)
    .reduce((count, price) => {
      return count + ((budget -= price) >= 0);
    }, 0);
}

정렬하여 예산을 오름차순으로 만드는 것은 같다.
자바스크립트의 특징(나쁜 특징이라고 생각 됨)은 true가 덧셈, 뺄셈과 같은 연산에서 쓰일 때는 1이 되고, false은 0이 된다. 이를 이용하여 count변수에 1또는 0을 계속 더하고 있다.
위의 Array.reduce()메서드는 결국 count를 반환한다.

재밌고 신박한 풀이이다. 그러나! count에 0를 더하는 것은 의미가 없는 과정이다. 그래서 더 이상 count값이 증가되지 않으면 함수를 종료하는 것이 효율적이다. 하지만 위에서는 d의 배열 길이 만큼 계속 반복을 하기 때문에 해당 코드가 효율적인가? 라고 하면 아닐 듯 하다. budget과 d배열이 간소할 경우는 큰 차이가 없겠지만 d 배열의 길이가 엄청 많이 길다면 실행속도에서 차이가 벌어지지 않을까?

결과

6. Conclusion

예산 문제는 쉽게 풀었다. 시간도 지금까지 풀었던 문제 중에 가장 짧게 걸렸다. 문제 차제도 쉬었고 복잡한 계산이 들어가지 않았기 때문에 가능했던 일이라고 생각한다. 나 뿐만 아니라 스터디 팀원들도 후딱 풀어서 빠르게 이야기를 나누었다. 쉬운 묹제였다고 바로 넘어가는 것이 아니라, 리팩토링과 다른 사람 풀이를 통해 다양한 풀이방법과 색다른 생각을 배워야 한다. 그래서 문제마다 이렇게 정리하는 것이기도 하다. 내일은 Level2를 정리할 텐데 시간이 오래 걸릴 것이다. 하지만 하루 종일 걸린다해도 확실히 내것으로 만들고 넘어가자.🙂

📅 2022-08-13

Previous두 개 뽑아서 더하기 Next신고 결과 받기

Last updated 2 years ago