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

KHW·2021년 2월 18일

목록 보기

6/37

문제 : 최고의 집합

기본적인 내용

일단 문제가 좀 모호하다 느꼈다.
예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.
만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.

이게 다시 말해서 곱이 최대인 집합이 없이 집합이 1개만 있으면 이건 최고의 집합이 되는건가의 의문이 일단 들었는데 어떻게 결국 풀긴했다. (여러 시도는 했다...)

생각해야 할 것

모든 인원에게 균등하게 나누고 남는 것을 1개씩만 몇몇애들에게만 주기
ex) 23를 4명으로 나누려면 [5,6,6,6] 형태를 만들어야 한다.

즉, 23 % 4 = 3이 된 3명만 기존 균등히 나눈 5개에서 1씩 추가된 값을 얻을 수 있다.

이를 식으로 표현하면

`Math.floor(s%n)인 애들만 Math.floor(s/n)개에서 1개 씩 추가된 값을 얻는다.

그외의 n명에서 나머지 인원(n-Math.floor(s%n))들은 Math.floor(s/n)개를 얻을 수 있다.

이를 식으로 정리하면

for(let i=0;i<n-Math.floor(s%n);i++)
      arr.push(Math.floor(s/n))
for(let i=0;i<Math.floor(s%n);i++)
      arr.push(Math.floor(s/n)+1)

이렇게 정리된다.

예외사항

기존의 존재하는 자연수 s보다 n의 값이 더 크다면 (n마다 기본적으로 1이상도 나눠줄수 없다면) 최고의 집합을 구할 수 가 없으므로 맨앞에 예외처리를 해준다.

  if(n>s)
        	return [-1]

코드

function solution(n, s) {
    	let arr=[];
        if(n>s)
        	return [-1]

         for(let i=0;i<n-Math.floor(s%n);i++)
                arr.push(Math.floor(s/n))
         for(let i=0;i<Math.floor(s%n);i++)
                 arr.push(Math.floor(s/n)+1)
         return arr;
}