[프로그래머스 lev3/JS] 최고의 집합

문제 출처

프로그래머스 lev3 - 최고의 집합

나의 풀이

1차시도 (실패/시간초과)

중복 집합이므로 중복을 허용한다.
n과 s의 크기가 크므로 dfs는 당연히 시간초과가 발생한다...

function solution(n, s) { 
  let tmp = []
  let set = new Set()

  const dfs = (target, sum) => {
    if(tmp.length > n || sum > s) return
    if(tmp.length === n && sum === s){
      set.add(JSON.stringify(tmp.sort((a,b)=>a-b)))
    }
    else{
      for(let i=1; i<=target; i++){
        tmp.push(i)
        dfs(target-i, sum+i)
        tmp.pop()
      }
    }
  }
  
  dfs(s, 0)
  if(set.size === 0) return [-1]

  let answer = Number.MIN_SAFE_INTEGER
  let result = []

  for(let x of set){
    let arr = JSON.parse(x)
    let current = 1

    for(let i=0; i<arr.length; i++){
      current *= arr[i]
    }

    if(answer < current){
      answer = current
      result = arr
    }
  }
  return result  
}

console.log(solution(3, 9)) // [1, 4]
// console.log(solution(2, 9)) // [4, 5]
// console.log(solution(2, 1)) // [-1]
// console.log(solution(2, 8)) // [4, 4]

다른 풀이 1

function solution(n, s){
  const share = s / n >> 0; 
  if(!share) return [-1];
  
  const rest = s % n;
  const answer = new Array(n).fill(share);
  
  for(let i=0; i<rest; i++){
    answer[answer.length -1 -i]++;
  }
  return answer; 
}

원소의 곱이 최대가 되려면, 원소들 간의 차이가 최소가 되어야 한다. 이때 원소들의 초기값을 s/n으로 균등하게 할당하고 시작하면 된다.

이때 각 원소에는 자연수가 들어가야 하므로 반올림하거나 내림 처리를 해줘야 한다.

참고
(number) >> (count) : (number)를 (count)번 2로 나누기 == 즉 2^(coount)
(number) << (count) : (number)를 (count)번 2로 곱하기

위 코드에서 s/n >> 0 이면
s/n을 1(2^0)로 나누는 것과 같다. 그러므로 share는 자연수가 된다.

자연수로 배치하기 위해 s를 n으로 나눈 값을 배열에 할당하다보면, 남은 값(나머지)이 발생한다.

합이 s가 되어야 하는데 나머지가 발생하면 안 되므로 이 나머지들을 배열에 추가해줘야 한다.

이때 오름차순으로 return해야 하므로
s%n만큼 for반복문을 순회하되, 뒤에서부터 answer 값을 1씩 추가하면 된다.

function solution(n, s) {
  if (n > s) return [-1];
  const mid = Math.floor(s / n);
  const answer = new Array(n).fill(mid);
  
  for (let i=0; i<s % n; i++) {
      answer[answer.length - 1 - i]++;
  }
  return answer;
}

다른 풀이 2

function solution(n, s) {
  var answer = [];
  if (n > s) {
    return [-1];
  }

  for (let i = 0; i < n; i++) {
    const number = Math.round(s/(n-i));
    answer.push(number);
    s = s - number;
  }
  return answer;
}

참고

Javascript 로 푸는 최고의 집합 알고리즘 - Martin