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

문제

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

프로그래머스

 

---

 

문제 개요

주어진 자연수의 개수 n과 합 s를 만족하는 집합 중, 각 원소의 곱이 최대가 되는 집합을 구하는 문제입니다. 만약 해당 조건을 만족하는 집합이 없다면 [−1]을 반환합니다.

 

접근 방법

1. 조건 확인
   • n>s인 경우, 합 s를 만들 수 없으므로 [−1]을 반환합니다.
2. 최적의 분배 계산
   • 합 s를 n개의 원소로 최대한 고르게 나누는 것이 곱을 최대화하는 방법입니다.
     • 각 원소에  s/n을 할당합니다.
     • s%n의 나머지 값은 각 원소에 하나씩 분배하여 고르게 분포되도록 합니다.
3. 결과 생성
   • 나눗셈의 몫으로 초기화된 배열에서, 나머지 개수만큼 앞에서부터 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;
    }
}