관리 메뉴

솜씨좋은장씨

[Programmers] 최고의 집합 (Python) 본문

Programming/코딩 1일 1문제

[Programmers] 최고의 집합 (Python)

솜씨좋은장씨 2020. 12. 22. 20:50
728x90
반응형

1일 1문제 280일차!

오늘의 문제는 프로그래머스의 최고의 집합 문제입니다.

 

코딩테스트 연습 - 최고의 집합

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

programmers.co.kr

Solution

def solution(n, s):
    answer = []
    
    if s // n < 1:
        answer = [-1]
    else:
        s_n = s // n
        
        for i in range(n):
            answer.append(s_n)
        s_p_n = s % n
        
        idx = len(answer) - 1
        
        for i in range(s_p_n):
            answer[idx-i] = answer[idx-i] + 1
    
    return answer

Solution 해설

먼저 n이 2 s가 1인 경우처럼 n개의 숫자로 s를 만들 수 없는 경우에는 [-1] 을 정답으로 return 하도록 합니다.

그렇지 않은 경우

먼저 정답 리스트 속 원소의 개수가 n개가 되도록 만들어 줍니다.

이렇게 하는 이유는 최대의 곱을 만들기 위해서는 최대한 균일한 숫자를 분포시켜주는 것이 중요하기 때문입니다.

s를 n으로 나눈 숫자를 만들어주고 이 숫자가 1이상인 경우

가장 뒤의 원소부터 1을 더해주도록 합니다.

 

SOMJANG/CODINGTEST_PRACTICE

1일 1문제 since 2020.02.07. Contribute to SOMJANG/CODINGTEST_PRACTICE development by creating an account on GitHub.

github.com

Comments