[프로그래머스] 최고의 집합 Java 풀이 및 해설

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

프로그래머스

 

풀이 방법

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

각 원소들의 크기가 균등하게 일정하게 분포되어있으면 모든 원소의 곱이 최대가 된다.

 

원소의 합 S가 주어졌을때 N개로 나눠 분배할때 균등하게 분포를 해주면 된다.

나눠야할 원소의 합 S가 있을때 N으로 나눈다면 균등하게 분포할 수 있는 값이 된다.

 

위의 개념을 활용해서

현재 idx 위치의 집합 원소를 배정할때

현재 배분해야할 원소의 총 합을 남은 원소 자리의 개수로 나누어

idx 위치에 값을 배정하면 된다.

 

이 다음 위치 idx+1의 위치에서는

남은 원소의 자리의 개수는 - 1로 감소하며

배분해야할 원소의 총 합은 idx 위치에 배정한 값을 뺀 값이 된다.

 

위의 방법을 반복해서 집합의 원소를 끝까지 채워나가면 자연스럽게 오름차순으로 최고의 집합을 완성할 수 있다.

 

전체 코드

class Solution {
    public int[] solution(int n, int s) {
        int[] answer = null;
        

        if(n>s) { // n:2 s:1과 같은 경우 집합을 채울 수 없음.
            answer = new int[1];
            answer[0] = -1;
        } else { // 집합을 1로 다 채우고 남은 원소를 채우면 되니깐 어떻게든 가능함.
            int[] arr = new int[n];
            
            // 채울 집합의 인덱스
            int idx = 0;
            while(n!=0) {
                arr[idx] = s/n;
                s -= arr[idx];
                n--;
                idx++;
            }
            
            answer = arr;
        }
        return answer;
    }
}