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

최은우·2023년 7월 27일
0

Algorithms

목록 보기
8/14
function solution(n, s) {
  const q = parseInt(s / n);
  const r = s % n;

  if (q === 0) {
    return [-1];
  }

  const answer = Array(n).fill(q);
  for (let i = n - 1; i >= n - r; i--) {
    answer[i]++;
  }

  return answer
}

문제 해석

합이 일정한 숫자들의 곱이 최대가 되기 위해서는 숫자들의 차이가 가장 적어야합니다.
이는 산술-기하 정리를 이용하여 어렵지 않게 확인할 수 있습니다.
따라서 주어진 's' 라는 숫자를 n개로 가장 균등하게 나눠야합니다.


풀이 과정

1. 균등하게 나누기 위해 s를 n으로 나눈 몫과 나머지를 구합니다.

2. 몫이 0이면 최고의 집합이 존재하지 않는 것이므로 [-1] 을 반환합니다.

예를 들어 n = 5, s = 3인 상황에서는
아무리 균등하게 나눠도 [0, 0, 1, 1, 1]로 나눌 수 밖에 없습니다.

3. 몫이 1보다 큰 경우에는 반환할 배열에 몫으로 채웁니다.

예를 들어 n = 3, s = 7 인 경우
몫이 2 이므로
answer = [2, 2, 2] 가 됩니다.

4. 이제 answer 배열의 뒤에서 부터 나머지 만큼 1씩 늘려줍니다.

예를 들어 n = 3, s = 8 인 경우
몫이 2, 나머지가 2 이므로
처음에는 answer = [2, 2, 2] 이고
나머지를 뒤에서부터 채운 후는 answer = [2, 3, 3]이 됩니다.


0개의 댓글