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

카테고리

?

나만의 카테고리

로직 짜기

문제 링크

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

요점

• 같은 합이 되는 수들의 곱이 최대 값이려면 각 값의 편차가 제일 작아야한다.

참고 지식

• 로직 떠올리기

풀이 (Java)

import java.util.*;

class Solution {
    public int[] solution(int n, int s) {        
        int quotient = s / n;
        int remainder = s % n;

        if (quotient > 0) {
            int[] answer = new int[n];
            for (int i = 0; i < n; i++) {
                if (n - remainder == i) {
                    quotient++;
                }

                answer[i] = quotient;
            }

            return answer;
        }

        return new int[]{-1};
    }
}

 

1. n개의 원소를 가진 집합의 원소들을 전부 합했을 때 특정 합을 가지려면 s / n 의 값들로 가능한한 채워야 하므로 몫을 구해준다.
2. 나눈 나머지의 값만큼 집합의 원소들을 1씩 증가시켜주면 최대로 편차가 작은 집합이 만들어진다.
3. 증가시킬때 오름차순으로 해야하기 때문에 배열에 입력할 때 나머지의 값과 남은 반복 횟수가 같을 때부터 1 증가시켜 입력한다.

이 문제는 어느 카테고리에 속할 지 모르겠네요... 그래서 그냥 로직 자체를 기억해야겠네요...

추가

위 문제 풀이를 수학적으로 계산해놓은 분이 계시네요

blog.martinwork.co.kr/theory/2019/01/19/top-group-algorithm.html

 
 

알고리즘 초보가 정리한 글입니다 더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!