최고의 집합 [자바]

 

🧫 문제 분석

✔️ 출처

최고의 집합 level 3

📖 문제

 

각 원소의 합이 S가 되면서 각 원소의 곱이 최대가 되는 집합을 구하는 문제이다. 

 

각 원소의 곱이 최대가 되려면

각 원소의 값이 대체로 균일해야한다. 

 

즉, s를 n개의 원소로 나눈  균등한 값을 n개가 나눠 갖고,

s를 n으로 나눴을 때 나머지 만큼 원소에 더해준다. 

 

문제에서 오름차순 정렬로 반환하라는 것과

s를 n으로 나눴을때 나머지가 n을 넘길 수 없다는 걸 알고 있을 것이다. 

 

즉, 나머지 값을 횟수로 사용하여

집합 배열 맨 마지막 인덱스부터 거꾸로 나머지 값 횟수만큼 이동하면서  1씩 추가해주면 된다. 

 

ex)

n = 3, s = 17 이라 했을 때

17 /3 = 5 

answer = {5,5,5} 

17 % 3 = 2

 

2번 뒤에서부터 1씩 추가 

answer[2]++;

answer[1]++;

 

answer = {5,6,6}

 

이런 식의 로직이다. 

 

참고로 n > s면  무조건 -1 이다. 

s를 만드는데 n 개의 각 원소는 최소값이 1이다.  (문제에서 자연수라고 하였음)

 

그런데 n > s면 각 원소의 합이 s를 무조건 넘어선다. 

 

0 > s - n

 

---

🔅 문제 풀이

import java.util.Arrays;

class Solution {
    public int[] solution(int n, int s) {
        
        // n > s 면 자연수 n개로 s를 만들 수 없음. 각 원소가 최소값이 1인데 s가 n개수보다 작다면 불가능
        if (n > s) {
            return new int[] {-1};
        }
        
        int[] answer = new int[n];
        int num = s / n;
        
        Arrays.fill(answer, num);
        int tmp = s - (num * n); 
        
        // tmp 만큼 집합 뒤에서부터 1씩 추가해준다. 
        for (int i = n - 1; i >= n - tmp; i--) {
            answer[i]++;
        }
        
        return answer;
    }
}

 

❗ 오답노트 / 필요한 지식