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

문제

1. n개 원소의 합이 s가 되는 수의 집합 

2. 1번을 만족하면서 각 원소의 곱이 최대가 되는 집합

 

입출력 예 

풀이

다른 블로그을 참고하여 해당 문제의 풀이를 이해했다. 

 

1. 조건 2번을 충족하기 위해서는 s/n의 값을 각각의 원소로 가지고 있어야한다. 

2. s%n의 값은 각각의 원소에 +1씩 한다 

 

예를 들어 n = 3, s = 9 로 가정

9 % 3 = 0 -> 따라서 각가의 원소는 3이 된다. 

{3, 3, 3} => 9 * 9 * 9 = 729

{1, 4, 4} => 1 * 16 * 16 = 256

{2, 2, 5} => 4 * 4 * 25 = 400

.

.

.

이렇게 {3, 3, 3}일 경우 2번의 조건을 만족한다. 

 

그렇다면 나머지가 있는 경우를 살펴보겠다.

n = 3, s = 11

11 / 3 = 4

11 % 3 = 2

 

{3, 4, 4} = 9 * 16 * 16 = 2304

{2, 4, 5} = 4 * 16 * 25 = 1600

.

.

.

이렇게 나머지의 값을 1씩 나누어야 최대값을 얻을 수 있다. 

 

1차 시도

해당 법칙에 따라서 로직을 구현하였다. 

반복문을 2번 사용하였다. 

 

1번째 반복문 : 배열 초기화

2번째 반복문 : 나머지 +1

 

이 방식으로는 프로그래머스에서 유효성 검사에서 실패하였다. 

    public static int[] solution(int n, int s) {

        if (n > s)

            return new int[] { -1 };

        // 1. int 배열 초기화 -> s/n

        int[] answer = new int[n];

        for (int i = 0; i < answer.length; i++) {

            answer[i] = s / n;

        }

        // 2. 나머지가 있을 경우 +1

        for (int i = 0; i < s % n; i++) {

            answer[i]++;

        }

        // 3. 정렬

        Arrays.sort(answer);

        return answer;

    }

 

 

2차 시도

유효성을 위해 반복문 2개를 하나로 합쳤다 

(최종 코드가 2차 시도의 코드이다. )

해당 소스로 유효성 검사도 통과하였다! 

 

 

 

최종  코드

    import java.util.Arrays;

   

    public static int[] solution(int n, int s) {

        if (n > s)

            return new int[] { -1 };

        // 1. 배열, 나머지 값 선언

        int[] answer = new int[n];

        int remain = s % n;

        // 2. 배열 초기화 & 나머지 처리

        for (int i = 0; i < answer.length; i++) {

            if (remain != 0) {

                answer[i]++;

                remain--;

            }

            answer[i] += s / n;

        }

        // 3. 배열 정렬

        Arrays.sort(answer);

        return answer;

    }

 

 

프로그래머스 문제 

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

프로그래머스