프로그래머스(Programmers) : 최고의 집합 - python 풀이

🔴 문제 설명

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

• 각 원소의 합이 S가 되는 수의 집합
• 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합

예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있다.

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

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

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

🟠 접근 방법

• 1 <= n <= 10,000 이므로 O(NlogN)으로 구현해야 한다.
• 중복집합임에 주의, 각 집합의 원소는 중복될 수 있음
• 최고 집합이 존재하지 않는 경우는 S가 합으로 만들어지지 않는 집합
  => n보다 s가 더 작은 경우를 예외처리 해야 한다.
• 최대한 S를 큰 수로 토막 내는 것이 각 원소의 곱이 최대가 되는 집합이다.
  1. S를 N으로 나눈 몫을 m이라고 할때 집합에 m을 추가
  2. S-=m, N-=1
  3. N개의 수가 모일 때까지 반복 (= N≥0 일 때까지 반복)
  4. 정렬 후 반환
  

🟡 풀이 코드

from typing import List

def solution(n: int, s: int) -> List:

    answer:List = list()

    if n > s:               # 예외 : 최고의 집합이 만들어지지 않는 경우
        return [-1]

    while n > 0:            # 아래 과정을 통해 집합의 원소가 N개가 될 때까지 반복
        m = s//n                # S를 최대한 큰 수로 토막내야 한다.
        answer.append(m)        
        n -= 1
        s -= m

    return sorted(answer)   # 오름차순으로 정렬된 리스트를 반환

🙏 문제 접근 방법 및 코드에 대한 피드백과 질문은 환영입니다!

✏️ Algorithm Study

본 문제의 다른 풀이 및 피드백, 전체 문제 풀이 순서는 위 알고리즘 스터디 Repository에서도 확인 가능합니다.