프로그래머스, 최고의 집합(java)

문제 설명

원소의 수가 n인 집합들이 있다. 이때 해당 집합의 n을 전부 더하면 s가 된다. 해당 조건의 집합들 중 n을 전부 곱해서 최대 값이 되는 집합을 구하는 문제이다.

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

프로그래머스

문제 풀이

문제 자체가 어렵지는 않았는데, 시간 복잡도에서 곤란했던 문제였다.

 

일단 문제를 풀기 전에 -1을 반환해야 하는 조건은 n이 s보다 클 때이다. n개의 원소를 다 더해서 s를 만들어야 하는데, n이 s보다 커버리면 1을 넣어줘도 답이 나오지 않기 때문이다.

 

아무튼 예외 조건을 제외하고 문제를 풀어 보자면, 문제의 핵심은 원소를 전부 곱하면 최댓값이 나와야 한다는 부분에 있다.

 

곱하기를 할 때 최댓값이 나오기 위해서는 해당하는 원소들이 가능한한 숫자가 커야 한다. 예를 들어서 두 원소를 더해서 10이 나오는 집한에는 {1,9}, {5,5}가 있지만, {5, 5}의 원소를 곱한 값이 {1, 9}보다 크다. 즉, 각 위치에 있는 원소들이 최대한 커야 한다는 것이다.

 

이를 위해서는 나누기를 이용해야 한다.

 

같은 원소 2개를 더했을 때, 9보다 작거나 같은 최대의 수는 무엇일까? 바로 4이다. 이는 9/2를 이용해 구할 수 있다. 그러므로 첫 번째 값은 4가 된다.

 

이제 9에서 4를 빼서 그 다음 수를 구해줄 차례이다. 아까 총 2개의 원소를 이용했으니 이제는 1개의 원소만을 이용해야 한다. 한개의 원소를 더해서 5를 만들 수 있는 최댓값은 무엇일까? 바로 5이다. 그러므로 두 번째 값은 5가 된다. 

 

다른 예시를 들어볼까 n이 3이고 s가 10인 경우를 생각해 보자.

 

같은 원소 3개를 더해서 10보다 작거나 같은 수를 만들 수 있는 경우는 3이다. 그러면 10-3으로 값은 7이 되고 answer에는 3이 들어간다.

 

이제 같은 원소 2개를 더해서 7보다 작거나 같은 수를 만들 수 있는 경우는? 바로 3이다. 그러므로 7-3은 4가 되고 answer에는 3이 들어간다.

 

마지막으로 원소 1개를 더해서 4보다 작거타 같은 수를 만들 수 있는 경우는? 바로 4이다. 그러므로 4-4는 0이 되고 answer에는 0이 된다.

 

코드

java

import java.util.*;

class Solution {
    public int[] solution(int n, int s) {
        int[] answer = new int[n];
        
        if (n > s) {
            answer = new int[1];
            answer[0] = -1;
            return answer;
        }
        
        int index = 0;
        while(n > 0) {
            answer[index] = s/n;
            s -= s/n;
            n--;
            index++;
        }
        
        
        return answer;
    }
}

여담

위에서 나름 열심히 설명했지만, 솔직히 나도 본능적으로 푼 문제라 어떻게 설명하면 좋을지 모르겠다. 다른 사람들 풀이를 보면 answer에 s/n한 값을 전부 넣어준 다음 뒤에서부터 1을 더해주던데. 어쩌면 그 풀이가 조금 더 보기 편할지 모르겠다.