프로그래머스 최고의 집합 코드 및 해설 (파이썬)

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

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

 

💡 합이 일정한 집합의 원소끼리 곱이 최대가 되려면, 원소들의 값이 최대한 비슷해야 합니다. 

 

예를 들어, 합이 7이고 길이가 3인 자연수로만 이루어진 리스트를 생각해보면, 다음과 같이 4가지가 있습니다. 

[1, 1, 5], [1, 2, 4], [1, 3, 3],  [2, 2, 3]

이때 각 원소의 곱이 가장 큰 것은 [2,2,3]으로 각 원소의 편차가 가장 작은 경우입니다. 

 

따라서 우선 n을 s로 나눈 몫 n개로 이루어진 리스트를 만들고, 합을 s로 만들어주기 위해 n을 s로 나눈 나머지는 리스트의 끝 원소부터 하나씩 더해줍니다. 문제에서 오름차순으로 정렬된 리스트를 반환하라고 했으므로 끝 원소부터 더했습니다.
단, n이 s보다 큰 경우 합이 s인 n개의 자연수가 있을 수 없으므로 [-1]을 반환하도록 합니다.

 

def solution(n, s):
    # 최고의 집합이 존재하지 않는 경우 
    # 합이 s인 n개의 자연수가 존재할 수 없는 경우 
    if n > s:
        return [-1]
    
    # 원소들끼리 값이 유사해야 곱이 최대가 됨 
    # s를 n으로 나눈 몫과 나머지  
    share, res = s // n, s % n
    
    # n개의 몫으로 이루어진 result 
    result = [share] * n 
    
    # 합을 s로 만들어주기 위해 나머지를 각 원소에 배분해줌 
    # 오름차순으로 정렬하기 위해 -i 
    for i in range(1,res+1):
        result[-i] += 1
    
    return result