강의로 돌아가기
이산하

효율성 2,3번 문제

효율성 2번은 아마 테스트케이스와 답이 맞지 않는 것 같고,
3번은 c++ 로 통과 할 수 없는 것 같습니다.

vector horror(budgets.size()*budgets.size()*budgets.size());

이런식으로 일부러 메모리 초과 만들어가며 확인 해 본 결과

효율성 2번은 budgets 합 < M 일때 budgets 중 제일 큰 값을 출력 해주는 테스트케이스인 거 같은데
정답이 아니네요

3번 문제 확인 해본 결과
소팅 하는 것만으로도 시간 초과가 됩니다.

작성중인 코드―solution.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
#include <queue>

using namespace std;
bool comp(int a, int b){
    if( a < b)
        return false;
    return true;
}
int solution(vector<int> budgets, int M) {
    int answer = 0;
    int i;
    int sum = 0;
    int bigest =0;
    priority_queue<int,vector<int>,greater<int>> pq;

    for(int i =0 ; i< budgets.size(); i++){
        pq.push(budgets[i]);
        sum = sum+=budgets[i];
        if (budgets[i] > bigest)
            bigest = budgets[i];
    }
    if(sum < M)
        return pq.top();
    sort(budgets.begin(),budgets.end());
    if(pq.top() > M/budgets.size())
        answer =  M/budgets.size();
    while(pq.top() < M/pq.size()){
        M-=pq.top();
        pq.pop();
    }
    answer = M/pq.size();
    while(answer > pq.top()){
        M -=pq.top();
        pq.pop();
        answer = M/pq.size();
    }
    /*
    while(true){
        remain =M;
        for(int i =0 ; i < budgets.size();i++){
            if(budgets[i] < answer)
                remain -= budgets[i];
            else
                remain -= answer;
        }
        if(remain ==0){
            return answer;
        }
        if( remain <=0)
            return answer-1;
        answer++;
    }*/
    return answer;
}
1 개의 답변
Demi

안녕하세요.
Cpp 언어에서 일부 효율성 테스트케이스의 시간 제한이 restrict 하다는 의견이 많아, Cpp 언어 기준 시간 제한을 완화하였습니다.

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.