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

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

프로그래머스

코드

import java.util.*;

class Solution {
  public int[] solution(int n, int s) {
      if(n > s)
          return new int[]{-1};
      
      int[] answer = new int[n];
      for(int i=0; i<answer.length; i++)
          answer[i] = s/n;

      for(int i=0; i<s%n; i++)
          answer[i] ++;
      
      Arrays.sort(answer);
      
      return answer;
  }
}

풀이

문제와 예제들을 보고 직관적으로 접근했다. 

곱이 최대인 원소를 리턴해야하는데, 예제들을 보면 짝지은 값들이 가장 큰 수들로 이루어져있다.

그래서 주어진 s의 합을 n개로 나타낼때, 일단 s가 n으로 나누어 떨어지는 수로 나누고, 나머지 만큼 값을 더한다.

따라서 풀이법은 다음과 같다. 

 

♠ 만약 n>s 인경우 - 집합의 합보다 자연수의 개수가 많은경우

    ▶ 위의 경우 n개의 자연수를 이용해 s의 합을 만들 수 없으므로 -1을 리턴한다.

 

♠ 그 외의경우 리턴할 배열 answer의 모든값에 s/n 을 저장한다.

 

♠ 그 후 s%n 만큼 answer 배열의 모든 값을 1씩 증가시킨다.

 

 

위 풀이가 무슨소리냐면, 다양한 예시를 통해 보면 이해하기가 쉽다.

n = 3 , s = 13 인경우 세 개의 자연수를 이용해 합의 13이 되고, 곱이 최대인 원소 3개를 리턴해야 하는데,

먼저 리턴해야 하는 3개의 값은 4, 4, 5 이다.

 

 - s/n ===> 13/3 = 4 이다. 따라서 answer 배열의 모든 요소에 4를 저장한다.

 - answer = [4, 4, 4]

 - s%n ===> 13%3 = 1 이다. 따라서 answer 배열의 한개의 값만 1을 증가시킨다.

 - 그럼 answer = [4, 4, 5] 가 된다. 따라서 최대값이다.

 

 

n = 4, s = 15 인경우도 보자.

 - s/n ===> 3이다. 따라서 answer 배열의 모든 요소에 3을 저장한다.

 - answer = [3, 3, 3, 3]

 - s%n ===> 3이다. 따라서 answer 배열의 세 개의 값을 1씩 증가시킨다.

 - 그럼 answer = [4, 3, 3, 3]이 된다. 따라서 최대값이다.

 

마지막으로 오름차순으로 정렬된 배열을 리턴하므로 배열을 정렬해주면 된다.

(배열을 정렬하지 않고, 배열의 마지막 요소부터 +1씩 증가시키는 방법도 있다.)