[Javascript] 프로그래머스 - 최고의 집합

문제 설명

자연수 n개로 이루어진 집합 중,

1. 모든 원소의 합이 S가 되며
2. 각 원소의 곱이 최대가 되는
   집합을 찾아야 합니다.

---

제한 사항

• 집합을 오름차순으로 정렬해야 하며,
• 존재하지 않는 경우 [-1]을 반환해야 합니다.

---

해결 방법

알고리즘: 수학, 그리디

1. 최대한 균등한 값으로 분배
   • 곱을 최대로 만들려면 각 원소들이 최대한 균등해야 합니다.
   • mid = s / n 을 통해 가능한 최대한 균등한 값을 찾습니다.
2. 몫과 나머지 활용
   • mid = Math.floor(s / n) 로 기본 값을 정합니다.
   • sub = s % n 를 계산하여 일부 원소에 +1을 더해줍니다.
3. 배열 생성
   • n - sub개의 원소를 mid로 설정
   • sub개의 원소를 mid + 1로 설정
   • 이로 인해 자연스럽게 오름차순 정렬이 유지됩니다.

---

시간 복잡도

• O(n), 배열을 생성하는 과정이 한 번 수행되므로 선형 시간 복잡도를 가집니다.

---

구현 코드

function solution(n, s) {
  if (s < n) return [-1];

  const mid = Math.floor(s / n);
  const sub = s % n;

  return Array(n)
    .fill(mid)
    .map((v, i) => (i < n - sub ? v : v + 1));
}