프로그래머스 [Lv. 3] 최고의 집합 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(n, s) {
    let answer = [];
    if (s / n < 1) {
        answer = [-1];
    } else {
        const remainder = s % n;
        const share = parseInt(s / n)
        let tmp = Array(n).fill().map(() => share);
        for (let idx = 0; idx < remainder; idx++) {
            tmp[idx] += 1; 
        }
        answer = tmp.sort((a, b) => a - b);
    }
    return answer;
}

풀이 방법

1. s를 n으로 나눴을 때 0 보다 작으면 불가능 하므로 [-1]을 반환한다.
2. 클 경우
   1. 나머지를 구한다.
   2. tmp라는 배열에 몫을 넣어준다.
   3. 나머지를 범위로 만들고 1을 더해준다.
   4. 정렬하고 answer에 넣는다.
3. answer를 반환한다.

느낀점

• dfs로 조합을 먼저 떠올릴 수도 있었지만 그렇게 되면 시간 복잡도가 (s-n)!인가 여튼 시간 초과가 날 것 같았다.