[Lv.3] 최고의 집합

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] solution(int n, int s) {
        int div=s/n;
        if(div<1)
            return new int[]{-1};
//        List<Integer> ansList = new ArrayList<>();
        int remainder=s-div*n;
//        for (int i = 0; i < n; i++) {
//            ansList.add(div);
//        }
//        for(int i=0;i<remainder;i++){
//            ansList.set(ansList.size()-1-i,div+1);
//        }
        int[] answer = new int[n];
        for (int i = 0; i < n-remainder; i++) {
            answer[i]=div;
        }
        for(int i=n-remainder;i<n;i++){
            answer[i]=div+1;
        }


        return answer;
    }
}

문제 자체는 상당히 쉬웠던거같다.

합이 s가 되는 n개의 원소로 이루어진 집합 중 각 원소의 곱이 최대가 되기 위해선 원소들이 모두 최대한 커야 한다.

예시로 주어진 1,8 2,7 .. 4,5만 생각해봐도 원소들 각각이 최선의 값을 가지는게 2번 조건을 제일 만족하는 집합이 된다.

그렇기에 주어진 수 s를 n으로 나눠 모든 원소가 평균 값을 가지게 하고 그 값에서 남은 값을 집합 내 원소들에게 1씩 순서대로 나눠주면 되는 문제다.

 

처음엔 List로 구현했더니 효율성부분에서 시간초과가 발생했다.

List에 값을 전부 넣고 + 맨 뒤 부터 나머지만큼 1씩 쭉 더하고 + 정답을 반환할 때 stream.mapToInt로 변환해서

아무래도 시간초과가 난 것 같았다.

 

그래서, 배열로 풀어 냈더니 정답처리 되었다..

문제 자체가 좀 쉽다보니 시간기준이 좀 엄격하게 잡혀있는 것 같다.