[Python] 최고의 집합

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

프로그래머스

• 첫 번째 풀이

from functools import reduce

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield list(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield list(pool[i] for i in indices)
        
def multiply(arr):
    return reduce(lambda x, y: x * y, arr) 

def solution(n, s):    
    if n > s:
        return [-1]
    
    comb = list(combinations_with_replacement(range(1, s+1), n))
    
    filtered_set = []
    for i in comb:
        if sum(i)==s:
            filtered_set.append(i)
    
    max_product = 0
    answer = []
    for i in filtered_set:
        product = multiply(i)
        if product > max_product:
            max_product = product
            answer = i
            
    return answer

Combination을 전부 구해서 합을 구하고 곱을 구하고.... 시간이 너무 오래걸림..

수학적으로 생각을 해야하는데 그저 문제만 풀어보겠다고 해서 오히려 비효율적으로 돼버림.

 

• 다른 사람의 풀이

def bestSet(n, s):
    answer = []
    a = int(s/n)

    if a == 0:
        return [-1]

    b = s%n

    for i in range(n-b):
        answer.append(a)
    for i in range(b):
        answer.append(a+1)

    return answer

수학적으로 깔끔하게 푼 풀이가 있었음...

난 아직 멀었나..