[프로그래머스] 최고의 집합 (08.07)

문제

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

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

 

접근법

문제는 쉬운 편이었다.

문제에서 말하는 최고의 집합이 되기 위해선 모든 집합의 숫자가 다 비슷해야한다.

무슨 말이냐

만약 n=3이고 s=10이라고 가정했을때

{3, 3, 4}가 최고의 집합이 된다.

{2, 2, 6} , {2, 3, 7}, {4, 2, 4} 등등 어떠한 집합도 {3, 3, 4}보다 곱이 클 수가 없다.

그래서 내가 생각한 방식은 모든 리스트에 s에서 n을 나눈 값을 넣어 놓고

s에서 n을 나눈 나머지 값만큼 각 원소들에 +1씩 해주어 정답 배열에 옮겨 담는 것이었다.

답은 맞았지만 이 코드는 시간 초과가 났다.

답을 리스트에 넣었다가 다시 배열로 옮기는 작업 자체가 시간이 많이 걸린 듯 하다.

그래서 아예 배열에 더해주는 방식으로 바꾸니 잘 돌아갔다.

 

코드

import java.util.Arrays;

class Solution {
    public int[] solution(int n, int s) {
        if(s < n)
            return new int[]{-1};

        int[] answer = new int[n];

        int divide = s / n;
        int remainder = s % n;

        Arrays.fill(answer, divide);

        for(int i=n-1;i>=0;i--){
            if(remainder == 0)
                break;
            answer[i] ++;
            remainder--;
        }

        return answer;
    }
}