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

# 문제 원문

 

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

---

입출력 예

n / s / result

2	9	[4, 5]
2	1	[-1]
2	8	[4, 4]

 

# 문제 풀이

 

입력 받은 집합의 원소 갯수 n과 집합의 총합 s를 통해서 가장 큰 몫을 가지는 집합을 만들어서 반환하는 문제이다.

문제 설명에는 Set으로 표현하지만 실제로는 중복 원소를 허용하니 Set 구조가 아니다. 집합의 모든 원소 합인 s를 n으로 나누었을때 1부터 작을 경우 s로는 n개의 원소를 가진 집합을 만들지 못하니(소수 비허용) [-1]를 반환 해주어야한다.

그외는 입력 받은 s를 n으로 나눈 값을 n개 가진 1차원 배열을 만들고 입력 받은 s에서 n을 나눈 나머지를 배열의 원소에 1씩 더해준후 오름차순으로 정렬해주면 된다. (나머지가 n보다 크다면 나머지가 없을 것이고 있다면 n보다 작다는 간단한 원리) 레벨3 문제치고 매우 쉬운문제이다. 연습문제라서 그런거 같다.

 

# 솔루션 플로우

1. 입력 받은 s와 n의 나머지 re를 구한다.

2. 입력 받은 s에서 re를 제하고 n으로 나눈 num을 구한다.

3. num이 1보다 작을시 [-1]를 얼리리턴한다.

4. 입력 받은 n 길이의 1차원 배열 result를 생성하고 num으로 모두 채운다.

5. result를 1회 순환하면서 re(나머지)를 1씩 나누어준다.

6. 오름차순으로 정렬된 result를 반환해준다.

1. FP

function solution(n, s) {
    let re = s % n;
    const num = (s - re) / n;
    if (num < 1) return [-1];

    return new Array(n).fill(num)
        .map((num) => {
            if (re > 0) {
                re--;
                return num + 1;
            }
            return num;
        }).reverse();
}