최고의 집합

 

수학적인 직관만 있다면 쉽게 아이디어를 얻고 풀이할 수 있는 문제.

 

---

 

 

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12938

프로그래머스

 

---

 

Problem

정수 n, s 가 주어지며, 's 가 베이스가 되는 특정 조건'에 해당하는 n 개의 0이 아닌 자연수를 찾으면 되는 문제이다.

이때 n 개의 문자는 배열로 return 해야 하며, 오름차순으로 정렬 후 제출해야 한다.

 

'특정 조건' 이란 n 개의 숫자 합이 s 가 되면서, 각 숫자들의 곱이 최댓값이 되게 하는 n 개의 자연수들이다.

예를 들어 n = 3, s = 10 일 때의 예시는 다음과 같다.

 

 

즉, 합이 s 가 될 수 있는 자연수의 집합은 무수히 많지만,

그 중에서 곱이 최댓값이 되는 집합을 반환하라는 문제이다.

 
 

Idea

사실 직관적으로 각 수의 차가 가장 적은 집합이 곱이 최대가 된다는 것을 알 수 있었다.

(이 부분은 산술기하로 인해 증명이 가능하다는데, 추후 수정하여 서술하도록 하겠다)

 

예를 들면

 

다음과 같이 [1, 4] 의 경우에는 두 수의 차가 3이고, [2, 3] 의 경우에는 두 수의 차이가 1인데

이때 개별 수의 곱은 두 수의 차이가 작은 [2, 3] 이 최댓값이 되는 것이다.

 

따라서 정답은 [a, a, a... , a+1...] 형태로 최대 차이가 1이 되는 집합이 되며,

이때 집합의 원소의 개수가 n 개이므로,

 

• a = s/n (소수점을 버린 정수 값)
• a+1 은 s%n 개만큼 존재

두 가지 조건을 만족한다면 정답을 산출할 수 있다.

 

직관적으로 n = 3, s = 10 일 때의 정답 산출 플로우는 다음과 같이 진행된다.

 

 

 

 

 

Solution

나의 경우 어차피 정답 배열을 만들어야 하고, 해당 배열을 a 혹은 a+1 로 채워서 return 해야 하기 때문에,

미리 계산한 값으로 for 문을 역순회하며 한 번에 [배열 채우기 + 오름차순] 이 만족하도록 로직을 작성했다.

 

직관적인 플로우는 다음과 같다.

 

 

이때, 문제의 조건에 '원소는 자연수' 라는 조건이 포함됐으므로,

만약 a 가 0인 경우, 즉 s / n (몫) = 0 인 경우는 [-1] 을 반환해주는 검증 로직을 추가해주어야 한다.

 
 

Code

검증 로직 및 for 문의 역순회를 이용하여 풀이한 코드는 다음과 같다.

 

class Solution {
    public int[] solution(int n, int s) {
        
        int quotient = s / n;   // 몫
        int remainder = s % n;  // 나머지
        
        // 몫이 0인 경우 -1 반환
        if(quotient == 0) {
            return new int[] {-1};
        }
        
        
        int[] answer = new int[n];
        
        // for 문을 역순회하며 remainder 만큼 a+1 을 채우고, 그 외에는 a 를 채우는 로직 
        for(int i=answer.length-1; i>=0; i--) {
            answer[i] = remainder-- > 0 ? quotient + 1 : quotient;
        }
        
        return answer;
    }
}

 

 

한 번의 for 문만을 돌았기 때문에 빠른 시간으로 해결할 수 있었던 모습이다.

 

 

End

수학적인 감만 있다면 쉽게 풀 수 있고 그래서 나도 해결할 수 있었지만,

정확한 수학적인 검증과 증명을 알지 못하고 감으로만 풀었기 때문에 조금 아쉬운 문제였다.

다만 여러 케이스를 생각해보고 그들 간의 규칙을 찾는 연습 용으로는 괜찮았다.

조금 더 어려운 문제를 풀어보자.