프로그래머스: 최고의 집합 [JAVA]

문제 링크

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

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

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 길이 n만큼의 배열을 생성
2. s를 n으로 나눈 몫을 각 배열 요소에 넣고, 남은 나머지 개수만큼 배열 요소들에 +1

 문제에서 요구하는 각 원소의 합이 s만큼이고 곱이 최대가 되기 위해서는, 각 요소들이 최대한 s/n이 되도록 고르게 나누어져야 한다. 그렇기 때문에 s/n의 값이 0이라면 애초에 불가능하기 때문에 {-1}을 반환하고, 그게 아니라면 n 개수만큼의 길이를 가진 answer 배열을 모두 s/n으로 초기화한 다음 나머지만큼 배열의 끝에서부터 +1을 해주면 전체적으로 고르게 펴진 집합을 가질 수 있다.

 

class Solution {
    public int[] solution(int n, int s) {
        int[] answer;
        int quotient = s / n; //몫
        int remainder = s - quotient * n; //나머지

        if (quotient == 0) {//애초에 몫이 0이면
            return new int[]{-1};
        }

        answer = new int[n];
        Arrays.fill(answer, quotient);
        for (int i = 1; i <= remainder; i++) {
            answer[n - i] += 1;
        }

        return answer;
    }
}

결과