프로그래머스 Lv.3) 최고의 집합

최고의 집합

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

풀이

중복 집합이라는 조건 때문에 비교적 간단한 문제였다.

문제는 3가지 조건으로 정리할 수 있다.

 

1. 입력받은 자연수 n개로 이루어진 중복 집합(Answer)을 구한다.
2. Answer의 각 원소의 합 : 입력받은 S가 되어야 한다.
3. 각 원소의 곱(즉 전체 원소의 곱)이 모든 경우의 수 중 최대가 되야한다.

이 세 조건을 충족시키는 중복 집합을 구하는 것이다.

 

Answer를 구할 수 없을 때는, [-1]을 리턴해야하는 조건도 추가적으로 있다.

-1을 리턴하는 경우는 주어진 N개의 수로 합 S를 만들 수 없는 경우다.

즉, S를 N으로 나눴을 때, 1 이상이 나와야 집합을 만들 수 있다는 소리다.

 

그래서 S를 N으로 나눈 몫 DIV와 나머지 MOD를 미리 구해 저장해주었다.

 

DIV가 0이라면 구할 수 없는 조건이기 때문에 answer를 -1 하나가 담긴 배열로 초기화 해준다.

DIV가 1 이상이라면 우선 모든 배열의 인덱스에 DIV 값을 저장해준다.

그리고 남은 MOD의 갯수에 따라 배열의 끝에부터 1씩 더해준다.

 

이렇게 진행한 이유는 연속하는 집합에서 곱이 최대값이 되려면, 평균값과 가장 근처에 있는 숫자들이어야 하기 때문이다.

N=2, K=8 일 때 ~> 4,4가 최대값, N=2, K=9일 때 ~> 4,5가 최대값

K=9인 경우에, MOD가 1이 남게되는데, 배열의 맨 끝의 인덱스를 1만큼 추가해주면 된다.

 

N=3, K=11일 경우를 살펴보자.

DIV = 3, MOD =2가 남게 된다.

그럼 answer에 {3,3,3} 을 초기값으로 넣어준다.

이후에 MOD가 2만큼 남아있으므로 끝에서부터 두번째 IDX까지 각각 1씩 더해주어 {3,4,4}를 만든다.

 

MOD가 남은만큼 하나에 다 넣어주면 더 크지 않을까 싶으신 분들은 위의 조건에서 {3,4,4}와 {3,3,5}를 살펴보면 명확해질 겁니다.

3x4x4 = 48 > 3x3x5 = 45, 즉 모든 값이 평균과 가까워야 더 큰 값이 됩니다.

 

로직

1. S를 N으로 나눈 몫 = DIV, 나머지 = MOD를 구해준다.

2. n크기의 answer 배열에 모두 DIV 값을 넣어준다.

3. answer 배열의 끝에서부터 MOD의 수 만큼, 각 배열에 +1을 해준다.

 

 

코드

class Solution {
    public int[] solution(int n, int s) {
        int[] answer;
        int div = s/n;
        int mod = s%n;
        if(div ==0) {   // 존재하지 않는 경우
            answer = new int[]{-1};
        } else {    // 존재하는 경우
            answer = new int[n];
            for(int i=0; i<n; i++) {
                answer[i] = div;
            }
            for(int i=1; i<=mod; i++) {
                answer[n-i]++;
            }
        }
        return answer;
    }
}