[12938] 최고의 집합

✔ 최고의 집합

[프로그래머스 12938]

문제 분석하기

s가 n으로 나누어 떨어진다면, n 나눈 값들의 곱이 가장 최대의 값이 되고

s가 n으로 나누어 떨어지지 않는다면, n 나눈 값들에 나머지만큼 1씩 증가시켜주도록 함

 

예1) s = 9, n = 3

[3, 3, 3] = 27

[4, 2, 1] = 8

 

예2) s = 10, n = 3

[3 + 1, 3, 3]

손으로 풀어보기

1. s가 n으로 나누어 떨어진다면, n 나눈 값들의 곱이 가장 최대의 값이 되므로 이 배열을 오름차순 정렬하여 반환
2. s가 n으로 나누어 떨어지지 않는다면, n 나눈 값들에 나머지만큼 1씩 증가시켜 이 배열을 오름차순 정렬하여 반환

슈도코드 작성하기

n(집합의 원소의 개수)
s(모든 원소들의 합)
answer(최고의 집합)
if(n이 s보다 크다면)
    최고의 집합을 만들 수 없으므로 -1을 담은 배열 반환
for(i -> n의 길이만큼) {
    s / n을 answer[i]에 저장
}
for(i -> s를 n으로 나눈 나머지만큼) {
    answer[i]를 1 증가
}
answer을 오름차순 정렬
answer 반환

코드 구현하기

/**
 * 12938) 최고의_집합
 */
public class L011_12938 {
    // n(집합의 원소의 개수)
    // s(모든 원소들의 합)
    public int[] solution(int n, int s) {
        // n이 s보다 크다면
        if (n > s)
            // 최고의 집합을 만들 수 없으므로 -1을 담은 배열 반환
            return new int[] { -1 };
        // answer(최고의 집합)
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            // s / n을 answer[i]에 저장
            answer[i] = s / n;
        }
        for (int i = 0; i < s % n; i++) {
            // s를 n으로 나눈 나머지만큼 answer[i]를 1 증가
            answer[i]++;
        }
        // answer을 오름차순 정렬
        Arrays.sort(answer);
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L011_12938 solution = new L011_12938();

        int n = 2;
        int s = 9;

        int[] result = solution.solution(n, s);

        System.out.println(Arrays.toString(result));
    }
}