2024.04.27 - 최고의 집합

[wlsgh7608]

문제 - 링크

문제 풀이

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.
각 원소의 합이 S가 되는 수의 집합
위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

• 최고의 집합 구하기

최고의 집합 구하기

• 최고의 집합이 되기 위해서는 집합의 각각의 원소가 골고루 분배되어야 함

코드

class Solution {
    public int[] solution(int n, int s) {
        // n개의 자연수로 s를 만들 수 없는 경우
        if (n > s) {
            return new int[]{-1};
        }

        // 각 원소가 골고루 분배되어야 함

        int[] answer = new int[n];

        int div = s / n;
        int remainder = s % n;

        // 오름차순으로 정렬되어야 하므로 오른쪽부터 시작
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = div;
            if (remainder-- > 0) {
                answer[i] += 1;
            }
        }

        return answer;
    }
}

시간, 공간 복잡도

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(N)

실행 시간