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

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

프로그래머스

코딩테스트 연습 > 연습문제 > 최고의 집합

 

문제 설명

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

 

각 원소의 합이 S가 되는 수의 집합
위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

 

제한 사항

최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다.
모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

 

 

문제 접근

조금만 생각하면 아주 간단한 문제이다.

 

n = 2 s = 9  최고의 집합 : {4, 5} 

n = 2 s = 9  집합들 : { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }

 

입출력 예를 보면 선택된 숫자가 서로 가까울수록 곱셈이 커지는 걸 알 수 있다. 

이걸 바탕으로 문제를 푼다.

 

s를 n으로 나눈다. 

9 / 2 = 4 ... 1 이다. 

4 + ( 4 + 1 ) = 9 

나머지가 m이라고 가정하면 m개는 몫 + 1을 해주면 된다. n - m개는 몫  
예)

n = 3 n = 11 

11 / 3 = 3 .. 2     

{3, 3+1, 3+1} -> 11 

 

이게 최고의 집합일까?  3 * 4 * 4 = 48 

 

대충 암산으로 계산해도 3 * 4 * 4 보다 큰 조합은 없을듯하다. 

 

자 이제 그럼 -1을 출력해야 하는 상황을 생각해 보자 언제일까?

 

s를 n으로 나누었는데 몫이 0면 집합을 만드는 게 불가능한 상황이다. 

이유 : 몫: 0은 자연수가 아니다.

 

예)

1 / 2 = 0 .. 1 

{0, 0+1} 

 

자 이제 구현을 하자.

 

프로그래머스는 제한 사항에 정확한 제한 시간이 없어서 아쉽다. 

그래서 항상 돌려보고 효율성 테스트에서 통과를 못하면 개선을 하는 방식으로 한다. 

이 문제 같은 경우는 n = 10000 이어서 어떻게 짜더라도 구현만 하면 통과할듯한데 아니었다.

정렬 컬렉션, 정렬 없이 순수 배열만 사용해야지 통과가 가능하다.

 

시간초과 코드(효율성 테스트 1/5 정확성 테스트 통과)

import java.util.*;
class Solution {
    public int[] solution(int n, int s) {
        if(s / n == 0) return new int[]{-1};
        else{
            int cnt  = s / n;
            int temp = s % n;
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++){
                if(temp == 0){
                    list.add(cnt);
                }
                else{
                    list.add(cnt + 1);
                    temp--;
                }
            }
            Collections.sort(list);
            int [] answer = new int [n];
            for(int i = 0; i < n; i++){
                answer[i] = list.get(i);
            }
            return answer;
        }
    }
}

 

 

정답 코드

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