[프로그래머스, 12938] 최고의 집합 (java)

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

프로그래머스

728x90

---

메모리: 53.9 MB, 시간: 0.40 ms

사용 알고리즘: 수학

 

집합의 모든 원소들이 수를 비슷하게 나눠가져야 곱했을 때 가장 큰 수를 얻을 수 있다.

따라서 모든 원소들이 s를 n으로 나누었을 때 몫을 기본으로 가지고

s를 n으로 나누었을 때의 나머지 값을 집합의 뒷 원소들이 1씩 나눠 갖는다.

(answer 배열을 오름차순 정렬한 후 리턴해야 하기 때문에, 뒷 원소들을 +1 해준다.)

import java.util.*;

class Solution {
    public int[] solution(int n, int s) {
        
        int[] answer;
        
        // 최고의 집합을 만들 수 없는 경우
        if(n > s) {
            answer = new int[] {-1};
            return answer;
        }
        
        answer = new int[n];
        
        // 모든 원소가 수를 골고루 나눠 가져야 유리
        int q = s / n; // 몫
        int r = s % n; // 나머지
        
        for(int i = 0; i < n; i++) {
            answer[i] += q;
            if(r-- > 0) answer[n - 1 - i]++; // 오름차순 정렬하기 위해 뒤에서부터 나머지를 더해줌
        }
        
        return answer;
    }
}