[lvl3]최고의 집합

출처: Programmers > 코딩테스트 연습 > 연습문제 > 최고의 집합

문제 설명:

자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 “집합”으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.

각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다.

{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }

그중 각 원소의 곱이 최대인 { 4, 5 }가 최고의 집합입니다.

집합의 원소의 개수 n과 모든 원소들의 합 s가 매개변수로 주어질 때, 최고의 집합을 return 하는 solution 함수를 완성해주세요.

[제한사항]

최고의 집합은 오름차순으로 정렬된 1차원 배열(list, vector) 로 return 해주세요.
만약 최고의 집합이 존재하지 않는 경우에 크기가 1인 1차원 배열(list, vector) 에 -1 을 채워서 return 해주세요.
자연수의 개수 n은 1 이상 10,000 이하의 자연수입니다. 모든 원소들의 합 s는 1 이상, 100,000,000 이하의 자연수입니다.

입출력 예:

n	s	result
2	9	[4, 5]
2	1	[-1]
2	8	[4, 4]

입출력 예에 대한 설명:

입출력 예 #1:

문제의 예시와 같습니다.

입출력 예 #2:

자연수 2개를 가지고는 합이 1인 집합을 만들 수 없습니다. 따라서 -1이 들어있는 배열을 반환합니다.

입출력 예 #3:

자연수 2개로 이루어진 집합 중 원소의 합이 8인 집합은 다음과 같습니다.

{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }

그중 각 원소의 곱이 최대인 { 4, 4 }가 최고의 집합입니다.

피드백:

효율을 극대화 하기 위해 간단한 경우인 n==s인 경우를 추가했더니 속도가 빠른걸 확인 할 수 있었다
원래 하고 싶었던 모든 경우의 수를 구하고 알고리즘을 이용하여 최적을 찾아가는 식으로 하지 않아서 우수답변자중에 그렇게 한 사람을 찾아보고 싶었으나, ..모두 나와 비슷한 형식으로 했다

코드설명:

합이 s인 n개의 자연수중 최대곱이 되는 자연수를 찾는 과정을 모든 경우의 수에서 최대곱을 찾는 과정으로 하고 싶었으나, 최대곱이 되는 조건을 알고있어서 바로 만들었다
최대곱이 되는 조건은 s를 최대한 비슷한 n개의 숫자로 나누는 방법이다
즉 n개의 s//n로 나누고, 마지막 수에 나머지를 더하면 최대곱을 만족하는 자연수르르 구할 수 있다
다만 나는 마지막 수에 나머지를 더하지 않고 s에서 s//n씩 빼는 형식으로 진행했다

코드:

  
def solution(n, s):
    answer = []
    if s<n: 
        return [-1]
    if n==s:
        return [s/n for i in range(n)]
    for i in range(n):
        num = s//(n-i)
        answer.append(num)
        s -= num
    return answer

우수답변자 코드:

  
# 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
# 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.
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

# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(bestSet(3,13))

우수답변자2 코드:

  
def solution(n, s):
    if s < n:
        return [-1]
    answer = []

    for _ in range(n - s % n):
        answer.append(s // n)
    for _ in range(s % n):
        answer.append(s // n + 1)
    return answer

우수답변자3 코드:

  
# 문제가 개편되었습니다. 이로 인해 함수 구성이나 테스트케이스가 변경되어, 과거의 코드는 동작하지 않을 수 있습니다.
# 새로운 함수 구성을 적용하려면 [코드 초기화] 버튼을 누르세요. 단, [코드 초기화] 버튼을 누르면 작성 중인 코드는 사라집니다.
def bestSet(n, s):
    answer = [0]*n

    average_number = int(s / n)
    slice_number = s % n

    if (n < s):

        for j in range(0, int(average_number)):
            for i in range(0, int(n)):
                answer[i] += 1

        for k in range(0, int(slice_number)):
            answer[k] += 1

        answer.sort()
        return answer

    else:
        answer.append(-1)
        return answer




print(bestSet(3, 13))