(javascript) 최고의 집합

코딩테스트 연습 - 최고의 집합 | 프로그래머스 스쿨

프로그래머스

 

s를 최대한 균등하게 나누면 최고의 집합이 된다. 왜냐면 수학적으로 그렇다.

x+y=s일 때, x*y의 최대값은 x=y일때다.

n이 3 이상일때도 해당되는지는 잘 모르겠지만 아무튼 그렇다.

 

따라서 n과 s의 최고의 집합은 모든 원소가 s/n일때다.

그런데 집합의 원소는 모두 자연수이므로, 모든 원소를 s/n의 몫으로 하고, s/n의 나머지를 하나씩 추가해주면 된다.

코드

function solution(n, s) {
    if (s < n) return [-1];
    var answer = [];
    var div = Math.floor(s / n);
    var r = s % n;
    console.log(r);
    for (var i = 0; i < r; i++) {
        answer.push(div + 1);
    }
    for (var i = 0; i < n - r; i++) {
        answer.unshift(div);
    }
    return answer;
}

 

결과

효율성 테스트에서 시간초과가 발생했다.

unshift가 비효율적인것 같다.

해당하는 부분을 수정했다.

코드

function solution(n, s) {
    if (s < n) return [-1];
    var div = Math.floor(s / n);
    var r = s % n;
    console.log(r);
    var answer = new Array(n - r).fill(div).concat(new Array(r).fill(div + 1));;
    return answer;
}

결과

끝