[프로그래머스] LV.3 최고의 집합/ 파이썬(Python)

📜 문제 설명

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

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

예를 들어서 자연수 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 이하의 자연수입니다.

 

🔗 문제 링크

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

프로그래머스

 

💡 문제 풀이

특정 숫자들을 더해서 타겟 수가 되는 조합들 중에 서로 곱한 결과가 최대수가 되기 위해서는 숫자들 간의 차이가 최소여야 한다.

위의 문제 설명 예시를 다시 보면 자연수 2개로 이루어진 집합들 중에 합이 9가 되는 집합들은 아래와 같다.

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

그리고 위의 집합들의 곱셈 결과는 각 8, 14, 18, 20이다. 두 수 간의 차이가 작을 수록 두 수를 곱한 결과는 커진다.

그리고 해당 특징은 모든 경우에 마찬가지이다. 숫자들 간의 차이를 최대한 작게 만들어주기 위해서는 아래의 로직을 구현하면 된다.

1. 우선 s를 n으로 나눈 값을 n개만큼 넣어준다 
2. s를 n으로 나눈 나머지의 갯수만큼 숫자들마다 1씩 더해준다
   이 때 오름차순 정렬을 위해서 리스트의 뒤에 있는 숫자들부터 1씩 더한다

def solution(n, s):
    answer = []
    
    # s : target number
    # n : numbers should be added together
    
    # 최고의 집합이 존재하지 않는 경우에 대한 예외처리
    if s < n:
        answer.append(-1)
        return answer
    
    # 필요한 숫자의 갯수만큼 우선 수를 넣어준다
    for i in range(n):
        answer.append(s // n)
    
    # 위에서 우선 넣어둔 숫자들이 아직 더해서 n이 되지 않는 경우
    # s를 n으로 나눈 나머지의 수만큼 리스트의 뒤에서부터 1씩 더해준다
    if s % n:
        a = s % n
        for i in range(1, a + 1):
            answer[-i] += 1
    
    return answer

보기만 해도 기분좋은거~