[프로그래머스] 최고의 집합 -Java

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

코딩테스트 연습 - 최고의 집합

class Solution {
	    public int[] solution(int n, int s) {
	        int[] answer = new int [n];
	        int[] nums = new int [n];
	        
	        
	        int num=s/n;
	        if(num<=0) {
	        	answer=new int[1];
	        	answer[0]=-1;
	        	return answer;
	        }
	        else {
	        	for(int i=0; i<n; i++) {
	        		nums[i]=num;
	        	}
	        	
	        	int plus=s%n;
	        	
	        	for(int i=n-1; i>=0; i--) {
	        		if(plus--<=0) break;
	        		nums[i]++;
	        	}
	        	
	        }
	        return nums;
	    }
	}

소요시간 : 20분

 

로직을 살펴보면

 

1. s를 n으로 나누어서 균등하게 숫자를 분배한다.

2. 균등하게 분배하고 남은 숫자를 nums배열의 뒤쪽부터 접근하며 1씩 올려준다.

 

왜 이렇게 하냐면 만약 원소의 합이 6인 집합이 있다면 곱해서 가장 큰 수가 나오는 원소는 3*3입니다.

즉 곱해서 큰 수가 나올려면 차이가 크지 않은 수가 유리합니다 ( 1*6 = 6  2*4=8  3*3=9)

 

우선 원소들의 합 s를 집합의 갯수 n으로 나눠줍니다.

예를 들어 n : 4  s : 10 이라면 

10/4=2를 구해줍니다.

 

그리고 n의 갯수만큼 n/s를 넣어줍니다.

위의 예로 보자면 

 

nums : 2 2 2 2라는 숫자가 들어갑니다.

 

그 후 10(s) - 8(n/s를 균등하게 나눠준 수의 합) = 2를 뒤에서부터 더해줍니다.

 

nums : 2 2 3 3 처럼 말이죠! 이렇게 하시면 답이 금방 나옵니다!