[PCCP] Lv1: 예산(12982) 해설

문제

- 문제 링크: 예산

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: d의 길이

- sort(): O(NlogN)

- 반복문은 최악의 경우 모든 원소에 대해 반복하므로 시간 복잡도는 O(N)

- 최종 시간 복잡도: O(NlogN)

#include <algorithm>
#include <vector>

using namespace std;

int solution(vector<int> d, int budget) {
    sort(d.begin(), d.end()); // 벡터 d를 오름차순으로 정렬
    int count = 0; // 지원할 수 있는 부서의 개수를 세는 변수

    for (int amount : d) {
        if (budget < amount) {
            break; // 남은 예산이 신청한 금액보다 작으면 더 이상 지원할 수 없으므로 종료
        }
        budget -= amount; // 예산에서 신청한 금액 차감
        count += 1;
    }
    return count;
}

solution 2)

#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());
    for (int i = 0; i < d.size(); i++)
    {
        budget -= d[i];
        if (budget < 0)
            break;
        answer++;
    }
    return answer;
}

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: d의 길이

- Arrays.sort(d)의 시간 복잡도: O(NlogN)

- 반복문은 최악의 경우 모든 원소에 대해 반복하므로 O(NlogN)

- 최종 시간 복잡도: O(NlogN)

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        Arrays.sort(d); // 배열 d를 오름차순으로 정렬
        int count = 0; // 지원할 수 있는 부서의 개수를 세는 변수
        
        for (int amount : d) {
            if (budget < amount) {
                break; // 남은 예산이 신청한 금액보다 작으면 더 이상 지원할 수 없으므로 종료
            }
            budget -= amount; // 예산에서 신청한 금액을 차감
            count++;
        }
        return budget >= 0 ? count : count - 1;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: d의 길이

- d.sort(): O(NlogN)

- 반복문은 최악의 경우 모든 원소에 대해 반복: O(NlogN)

- 최종 시간 복잡도: O(NlogN)

def solution(d, budget):
    d.sort() # 배열 d를 오름차순으로 정렬
    count = 0 # 지원할 수 있는 부서의 개수를 세는 변수
    
    for amount in d:
        if budget < amount:
            break # 남은 예산이 신청한 금액보다 작으면 더 이상 지원할 수 없으므로 종료
        budget -= amount # 예산에서 신청한 금액을 차감
        count += 1
    return count if budget >= 0 else count - 1

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: d의 길이

- d.sort(): O(NlogN)

- 반복문은 최악의 경우 모든 원소에 대해 반복하므로 O(NlogN)

- 최종 시간 복잡도: O(NlogN)

function solution(d, budget) {
    d.sort((a, b) => a - b); // 배열 d를 오름차순으로 정렬
    let count = 0; // 지원할 수 있는 부서의 개수를 세는 변수
    
    for (const amount of d) {
        if (budget < amount) {
            break; // 남은 예산이 신청한 금액보다 작으면 더 이상 지원할 수 없으므로 종료
        }
        
        budget -= amount; // 예산에서 신청한 금액을 차감
        count++; 
    }
    
    return budget >= 0 ? count : count - 1;
}

solution 2)

import

solution 3)

import