문제

[프로그래머스] 최고의 집합
https://school.programmers.co.kr/learn/courses/30/lessons/12938

풀이

조건

• 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.
  • 각 원소의 합이 S가 되는 수의 집합
  • 위 조건을 만족하면서 각 원소의 곱이 최대가 되는 집합
• 집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

풀이 순서

• 문제에 있는 예시를 보면 가능한 집합 중 값들의 차이가 가장 작은 케이스로 이루어져 있다.

  예를 들어
  1) { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } -> { 4, 5 }
  2) { 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 } -> { 4, 4 }

• 입력받은 s를 n으로 나눈 몫으로 배열의 모든 요소를 초기화한다.
• s를 n으로 나눈 나머지를 배열에 1씩 나눠준다.
  • 이 때 배열의 마지막 요소부터 나눠주면 오름차순 정렬된 것과 같은 결과가 나온다.

코드

Java

class Solution {
    public int[] solution(int n, int s) {
        int[] answer;
        
        // n이 s보다 크면 불가능
        if(n > s) {
            answer = new int[]{-1};
            return answer;
        }
        
        int init = s / n; // 몫
        int mod = s % n; // 나머지
        
        answer = new int[n];
        // 몫으로 모든 값을 초기화
        for(int i = 0; i < n; i++) {
            answer[i] = init;
        }
        
        // 나머지 만큼 뒤에서부터(오름차순 정렬이 되게) 1씩 더해줌
        int idx = n - 1;
        for(int m = 0; m < mod; m++) {
            answer[idx]++;
            idx--;
        }
        
        return answer;
    }
}

정리

• 집합을 어떻게 구해야 할 지 어려움을 겪었었다.
• 문제에서 주어진 예시를 보고 최적의 값을 찾았다.
  • 그리디?