초보몽키의 개발공부로그

level 4. 최고의 집합

04 Oct 2017 | 알고리즘 프로그래밍

문제출처

문제

자연수 N개로 이루어진 집합 중에, 각 원소의 합이 S가 되는 수의 집합은 여러 가지가 존재합니다.
최고의 집합은, 위의 조건을 만족하는 집합 중 각 원소의 곱이 최대가 되는 집합을 의미합니다.

집합 원소의 개수 n과 원소들의 합 s가 주어지면,
최고의 집합을 찾아 원소를 오름차순으로 반환해주는 bestSet 함수를 만들어 보세요.
만약 조건을 만족하는 집합이 없을 때는 배열 맨 앞에 –1을 담아 반환하면 됩니다.
예를 들어 n=3, s=13이면 [4,4,5]가 반환됩니다.
(자바는 집합이 없는 경우 크기가 1인 배열에 -1을 담아 반환해주세요.)

풀이코드

  • 처음에는 itertools, functools 모듈을 임포트해서 주어진 길이와 합 조건에 맞는 모든 리스트의 경우의 수를 구했다.
  • 모든 경우의 수를 구하고 for 문을 돌리다 보니 실행시간이 오래 걸리는 문제가 발생한다.
  • 참 어렵게도 풀었다..

첫번재 시도 - 느리다

def bestSet(n, s):
    import itertools
    from functools import reduce
    if n > s:
        return [-1]
    combinations = [i for i in itertools.combinations_with_replacement(range(s+1), n) if sum(i) == s]
    multiply_li = [reduce(lambda x,y: x*y, combination) for combination in combinations]
    index = multiply_li.index(max(multiply_li))
    return sorted(list(combinations[index]))

두번째 시도

  • 첫번째 방법으로 풀고나니 이렇게 어렵게 풀 문제가 아닌것 같다는 생각이 들었다.
  • 단순한 예시를 사용해서 곱이 최대가 되는 경우를 살펴보니 각 요소의 편차가 가장 작을 때 곱이 최대가 되는것 같다.
def bestSet(n, s):
    if n > s:
        return [-1]
    portion, remainder = divmod(s, n)
    li = [portion] * n
    for i in range(remainder):
        li[i] += 1

    return sorted(li)

세번째 시도

def bestSet(n, s):
    if n > s:
        return [-1]
    portion, remainder = divmod(s, n)
    li = [portion] * n
    while remainder > 0:
        li[li.index(min(li))] += 1
        remainder -= 1

    return sorted(li)

Related Posts