[코딩테스트] 프로그래머스 - 최고의 집합

1. 아이디어 

▪ n = 2, s = 6 일때 [3,3]가 최대 곱 

▪ n = 3, s = 9 일때 [3,3,3]가 최대 곱 

▪ 즉, 원소 n개의 분포가 고를수록 집합의 곱이 크다는 점을 이용 -> Greedy 

▪ s보다 n이 클 경우 [-1] return 

▪ s를 n으로 나눈 몫과 나머지 값 구하기

▪ (n - 나머지 값) 번 만큼 answer 리스트에 몫을 append

▪ (나머지 값) 번 만큼 answer 리스트에 (몫+1)을 append

2. 시간복잡도

▪ O(n)

3. 변수

▪ 나머지, 몫: int 

Code

def solution(n, s):
    answer = []
    
    if n > s:
        return [-1]
    
    x = s // n
    remain = s % n
    
    for _ in range(n-remain):
        answer.append(x)
        
    for _ in range(remain):
        answer.append(x+1)
                        
    return answer

 

프로그래머스