[프로그래머스] 최고의 집합 (javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/12938

프로그래머스

 

🤔 해결방법

1. s를 n으로 나눈 몫으로 집합을 채운다.

2. 나머지가 나오는 경우 1씩 더해준다.

3. 오름차순으로 정렬 후 반환

 

 

🔑 풀이

문제를 처음 읽었을 때는 단순하게 합해서 S가 되는 쌍을 모두 찾아 곱하기까지 해보면 되지 않을까 싶었지만 당연히 메모리 초과, 시간 초과가 날 것 같았다.

그래서 곱의 결과가 최대가 되는 집합을 찾기 위해 어떤 규칙이 있는지 여러 예시로 알아봤다.

그 결과, n개의 숫자들 간의 차이가 적을수록 곱의 결과가 크다는 것을 알 수 있었다!

 

 

그렇다면 숫자들 간의 차이가 적은 쌍을 어떻게 찾아야 할까.

위의 예시들처럼 1,4,5번째의 경우 즉, s를 n으로 나누어 떨어지는 경우는 그 몫들로 이루어진 집합이 답이 된다.

2,3번째처럼 나누어 떨어지지 않는다면 나머지를 최대한 분배하면 된다.

이는 각 요소에 1씩 나머지만큼 더해주면 된다. 

따라서 최종 코드는 다음과 같다.

 

function solution(n, s) {
      let answer = [];

      //s가 n보다 작아서 집합을 만들 수 없는 경우
      if (s < n) {
          answer.push(-1);
          return answer
      }

      //나누어 떨어지는 경우
      if ( s % n === 0) {
          for (let i = 0; i < n; i++){
          answer.push(Math.floor(s / n));

      //나누어 떨어지지 않는 경우
      }} else {
          for (let i = 0; i < n; i++){
          answer.push(Math.floor(s / n));
          }
          //1씩 나머지만큼 더해줌
          for (let j = 0; j < s % n; j++){
              answer[j] += 1;
          }
      }

      //오름차순 정렬
      answer.sort((a,b) => a-b)

      return answer;
  }