(프로그래머스 c++)최고의 집합

vector<int> answer에 n만큼의 공간을 0으로 할당해준다.

그리고 비어있는 tmp 벡터도 선언한다.

 

만약 s < n이라면 최고의 집합이 존재하지 않는 경우이므로 tmp에 -1을 넣어주고 리턴.

for문을 통해 최고의 집합을 만들도록 한다.

n ~ 1까지 반복하며, q = s / i를 하여 answer의 앞에서부터 차례대로 몫을 넣어준다.

그리고 s -= q를 하여 다음 수를 구할 수 있도록 한다.

for문이 끝나고 마지막에는 s의 나머지 값을 넣어주고 리턴하면 된다.

 

answer를 n개로 미리 할당하는 이유는 효율성 테스트때문이다.

동적할당이라서 push_back 할 때마다 시간초과가 일어나므로 미리 n개만큼 할당하여 시간을 줄였다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer(n, 0), tmp;
    int q = 0;
    
    if(s < n)
    {
        tmp.push_back(-1);
        return tmp;
    }
    
    for(int i = n; i > 1; i--)
    {
        q = s / i;
        answer[n - i] = q;
        s -= q;
    }
    
    answer[n - 1] = s;
    return answer;
}