[프로그래머스] 12982 - 예산

Об этом предложении

문제 소개 프로그래머스 Lv.1 · 예산 부서마다 물품 구매에 필요한 신청 금액이 배열 d 로 주어지고, 회사의 전체 예산은 budget 이다. 각 부서에는 신청한 금액을 전부 주거나 아예 주지 않아야 하며, 일부만 지원할 수는 없다. 예산 안에서 최대 몇 개 부서를 지원할 수 있는지 구하는 문제다. 부서 수는 최대 100개, 신청 금액은 최대 100,000, 예산은 최대 10,000,000이다. 접근 방법 지원하는 부서의 개수만 최대로 만들면 되므로, 금액이 작은 부서부터 지원하는 것이 가장 유리하다. 같은 예산이라면 적은 금액을 쓸수록 남는 돈으로 더 많은 부서를 지원할 수 있기 때문이다. d 를 오름차순으로 정렬한다. 앞에서부터 차례로 보면서, 신청 금액이 남은 예산 이하이면 예산에서 빼고 지원 개수를 1 늘린다. 끝까지 돈 뒤 개수를 반환한다. 정렬해 두었기 때문에 한 번 예산이 모자란 순간부터는 뒤에 있는 금액도 전부 모자란다. 그래서 조건이 처음 실패할 때 break 로 반복을 끝내도 결과는 같다. 풀이 코드 import java.util.Arrays; class Solution { public int solution(int[] d, int budget) { int answer = 0; Arrays.sort(d); for (int i = 0; i < d.length; i++) { if(d[i] <= budget) { budget -= d[i]; answer++; } } return answer; } } 시간 복잡도 O(n log n). 정렬에 O(n log n)이 들고, 이후 배열을 한 번 순회하는 데 O(n)이 든다. 배운 점 배열을 정렬해 두면 이 문제를 간단하게 풀 수 있다는 것을 알게 됐다. 작은 금액부터 차례로 고르기만 하면 되기 때문이다.

Детали предложения

Провайдер

velog

Источник

velog-rss

Балл

54.4

Уверенность

49%