오늘은 프로그래머스의 최고의 집합이라는 문제를 풀었다.
문제 설명은 다음과 같다.
문제 설명
자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.
각 원소의 합이 S가 되는 수의 집합
위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
예를 들어서 자연수 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 이하의 자연수입니다.
이 문제는 합이 s가 되는 n개의 자연수 배열을 구하는 문제이다.
처음에 생각한 방법은 s를 n으로 나누어주고 나머지를 배열의 마지막 값에 더하려고 해보았다.
근데 여기서 생긴 문제가 나머지가 1일 때는 상관이 없지만 나머지가 1보다 크고 n보다 작은 경우 문제가 생긴다.
예를 들어보면 s가 11이고 n이 3일 때는 3, 3, 5라는 결과가 나오게 되서 정답인 3, 4, 4와 달라 틀리게 된다.
그래서 생각한 방법이 나머지가 나왔을 때 배열의 맨 뒤에서 부터 1씩 더해주는 방법이다.
풀이 코드는 다음과 같다.
class Solution {
public int[] solution(int n, int s) {
if (n > s) {
return new int[]{-1};
}
int div = (int)(s / n);
int mod = s % n;
int[] intArray = new int[n];
for (int i = 0; i < n; i++) {
intArray[i] = div;
}
for (int i = n - 1; mod > 0; i--) {
intArray[i] += 1;
mod--;
}
return intArray;
}
}우선 먼저 n이 s보다 크면 -1이 들어간 배열을 반환한다.
이유는 n이 s보다 크게되면 배열의 길이가 n인 자연수들을 만들 수 없기 때문이다.
그리고 s를 n으로 나눠준 후 정수로 저장하고 나머지도 저장해준다.
크기가 n인 정수 배열을 만들어주고 배열에 나눠진 값을 모두 넣어주고 뒤에서부터 나머지를 1씩 분배해주게되면 이 문제를 해결할 수 있다.
