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

문제

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

프로그래머스

 

---

문제 개요

주어진 자연수의 개수 n과 합 s에 대해, 각 원소의 합이 s가 되면서 각 원소의 곱이 최대가 되는 집합을 구하는 문제입니다. 만약, 그러한 집합을 만들 수 없다면 -1이 들어있는 배열을 반환해야 합니다.

 

접근 방법

1. 자연수 분배: s를 n개의 자연수로 최대한 균등하게 나누는 것이 각 원소의 곱을 최대화하는 방법입니다. 즉, 가능한 한 원소들의 값이 비슷해야 곱이 최대가 됩니다.
   • s를 n으로 나눈 몫을 각 원소에 먼저 할당하고, 나머지 값은 일부 원소에 하나씩 추가하여 균등하게 배분합니다.
2. 불가능한 경우 처리: 만약 n이 s보다 크다면, 원소의 합을 s로 만들 수 없으므로 -1을 반환합니다.
3. 정렬: 결과 집합은 오름차순으로 정렬된 배열이어야 하므로, 자연수 분배 후 정렬하여 반환합니다.

 

해결 과정

1. 초기 값 설정: 먼저, s를 n으로 나눈 몫을 모든 원소에 할당합니다.
2. 나머지 값 분배: s를 n으로 나눈 나머지 값을 첫 번째 원소부터 하나씩 더하여 자연수들의 차이가 최소화되도록 합니다.
3. 정렬 후 반환: 분배가 끝나면 배열을 오름차순으로 정렬하고 반환합니다. 만약 n > s인 경우에는 -1이 들어있는 배열을 반환합니다.

import java.util.*;
class Solution {
    public int[] solution(int n, int s) {
        int[] answer = new int[n];
        if (n > s) return new int[]{-1};        
        
        for (int i = 0; i < n; i++) {
            answer[i] = s/n;
        }
        
        for (int i = 0; i < s%n; i++) {
            answer[i]++;
        }
        
        Arrays.sort(answer);
        return answer;
    }
}