[알고리즘]프로그래머스 12938번 - 최고의 집합

프로그래머스 12938번 - 최고의 집합

프로그래머스 12938번 - https://programmers.co.kr/learn/courses/30/lessons/12938

 

요구사항

1. 자연수 n 개로 이루어진 중복 집합 중 최고의 집합을 오름차순으로 정렬하여 반환하라.

2. 자연수 n 개로 이루어진 중복 집합은 다음과 같다.

 

각 원소의 합이 S를 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 중복 집합 중 최고의 집합이라고 한다.

 

요구사항 분석 및  풀이과정

1. 자연수 n이 s보다 클 경우, 자연수 n개로 이루어진 중복 집합의 합은 무조건 s를 넘기 때문에 최고의 집합이 존재하지 않는다.

2. 자연수 n개로 이루어진 중복 집합의 합이 s로 일정할 때, 중복 집합의 각 원소의 곱이 최대가 되기 위해서는 각 원소 간의 편차가 적어야 한다. 왜 그런지 궁금하다면 싶다면 산술-기하 평균 부등식을 알아보자.

 

s가 n으로 나누어떨어지면 문제가 되지 않지만, 그렇지 않은 경우는 원래라면 그 나머지를 균일하게 모든 원소에 더해주면 된다. 위에서 말한 산술-기하 평균 부등식의 등호 성립 조건이 그렇다.

 

우리는 중복 집합의 원소가 자연수이므로 그러면 안 된다. 그렇기 때문에 각 원소 간의 편차를 줄이기 위해 나머지를 모든 원소에게 나누는 것이 아니라 1씩 나머지만큼 각 원소에 더해주면 편차를 최소화하며 각 원소의 곱이 최대가 되는 최고의 집합을 구성할 수 있다.

 

주의하여야 할 점은 최고의 집합을 오름차순으로 정렬하여 반환하여야 한다.

 

소스코드 작성

class Solution {

	public int[] solution(int n, int s) {
		if (n > s) {
			return new int[] {-1};
		}

		int[] result = new int[n];
		Arrays.fill(result, s / n);

		for (int i = 0; i < (s % n); i++) {
			result[i]++;
		}

		Arrays.sort(result);
		return result;
	}
}

 

결과

 

소스코드 깃허브 주소

링크