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

📌 Problem

중복이 가능한 자연수의 개수 N과 모든 자연수의 합 S가 주어진다. N개의 자연수 합이 S가 되는 것 중에 N개의 자연수 곱이 최대인 자연수 배열을 오름차순으로 정렬하여 반환하면 된다. 가능한 경우가 없으면 -1을 포함하는 배열을 반환한다.

📌 Solution

처음에는 백트래킹 방식으로 문제를 해결하였다. 솔루션 자체는 맞았지만 시간 복잡도 측면에서 굉장히 오래 걸리면서 통과를 하지 못했다. 그래서 좀 더 빠르게 해결할 수 있는 방법을 찾았는데 사실 비슷한 문제를 알고 있다. 둘레가 일정한 직사각형에서 최대 넓이를 만들고 싶으면 정사각형이 되어야 한다. 이 문제도 마찬가지이다. 모든 자연수가 최대한 동일할 때 최대곱이 완성된다.
이를 구현하는 것은 매우 간단하다. 모든 숫자를 S / N으로 초기화하고 S % N개의 숫자에 1씩 더하는 것이다. 다만, 시간 복잡도를 더 줄이기 위해서는 구분을 하며 초기화 하는 것이다. 즉, N - S % N개는 S / N으로 초기화하고 나머지는 S / N + 1로 초기화한다. 또한 index 0부터 차례대로 초기화하면 이후 정렬도 필요가 없다.

📌 Code

class Solution {
    public int[] solution(int n, int s) {
        if (n > s) return new int[]{-1};
        int[] nums = new int[n];
        for (int i = 0; i < n - s % n; i++) nums[i] = s / n;
        for (int i = n - s % n; i < n; i++) nums[i] = s / n + 1;
        return nums;
    }
}