[프로그래머스] 최고의 집합 자바 풀이

문제

문제 설명

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

1. 각 원소의 합이 S가 되는 수의 집합
2. 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.

{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }

그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

제한사항

• 최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
• 만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 1 을 채워서 return 해주세요.
• 자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
• 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

---

입출력 예

n s result

2	9	[4, 5]
2	1	[-1]
2	8	[4, 4]

입출력 예 설명

입출력 예#1

문제의 예시와 같습니다.

입출력 예#2

자연수 2개를 가지고는 합이 1인 집합을 만들 수 없습니다. 따라서 -1이 들어있는 배열을 반환합니다.

입출력 예#3

자연수 2개로 이루어진 집합 중 원소의 합이 8인 집합은 다음과 같습니다.

{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }

그중 각 원소의 곱이 최대인 { 4, 4 }가 최고의 집합입니다.

풀이

처음에는 문제만 읽고 중복 조합 문제라고 확신하고 문제를 풀었는데, 계속 시간초과가 나서 입력을 보니 n의 개수가 10,000 s가 100,000,000 이었다. 절대로 이렇게 풀면 안되는 문제였다.. n의 개수가 2에 s가 100,000,000 이라고 해도, 중복 조합을 이용했을 경우 s제곱만큼의 연산을 해야하므로.. 입출력을 잘 보고 문제를 풀도록 하자.

각 원소의 곱이 최대인 집합을 만들기 위해서는 각 원소들이 균등한 값을 가질 때 가장 높다. 첫번째 예제인 [4,5]만 봐도, [1,8], [2,7], [3,6], [4,5] 중에서 각 원소들의 차가 가장 적은 [4,5]의 곱이 가장 큰 것을 알 수 있다.

따라서 s / n으로 나눈 값을 전체 배열에다 채워준 후에 나머지값이 존재 할 경우 나머지 값의 크기만큼을 각 원소에 1씩 더해주면 된다. 이때 오름차순으로 정렬된 배열을 리턴해야 하므로, 전체 길이 - 나머지 값 부터 전체 길이까지 각 원소의 값을 1씩 더해주면 된다.

코드

import java.util.*;
class Solution {
   public int[] solution(int n, int s) {
        int[] answer;
        if (n > s) {
            answer = new int[1];
            answer[0] = -1;
        } else {
            answer = new int[n];
            int val = s / n;
            Arrays.fill(answer, val);
            if (s % n != 0) { 
                int a = s % n;
                for (int i = answer.length-a; i < answer.length; i++) {
                    answer[i]++;
                }
            }
        }
        return answer;
    }
}