[Python] 프로그래머스. 최고의 집합 (Level 3)

 

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

코딩테스트 연습 - 최고의 집합 | 프로그래머스

 

주어진 n과 s에서, 자연수의 개수 n보다 s의 크기가 큰 경우는 불가능하다. 자연수 5개로 3을 만드는 것이 불가능한 것처럼.

따라서 n이 s보다 큰 경우는 [-1]을 반환하면 된다.

 

숫자 s를 자연수 n개로 표현하면서 '곱이 가장 큰 수'가 되도록 하려면, n개의 각 자연수 간 차이가 적어야 한다.

 

숫자 s를 n으로 나눈 몫을 n개만큼 result 리스트에 저장하면 일단 곱이 가장 큰 조합이 만들어진다.

ex) 7을 3개의 자연수로 표현한다? -> [2,2,2] . (7 // 3 = 2)

이 때, s를 n으로 나눈 나머지가 남을 수 있다. 위 사례의 경우 나머지는 1이고, 문제의 조건인 '오름차순 정렬'을 충족시키려면 나머지 숫자만큼 result 리스트의 맨 뒤에서부터 숫자 1을 더해줘야 한다. [2,2,2]에서 맨 뒷 숫자부터 1씩 더해줘야 한다. 즉 위 사례에서는 최종적으로 [2,2,3]이 만들어진다.

 

마찬가지로, 8을 3개의 자연수로 표현하면 [2,2,2]에서 출발하고, 나머지가 2이므로 뒤에서부터 숫자 1씩 더해주면 된다. [2,3,3]이 최종 결과가 된다.

 

코드로 표현하면 아래와 같다,

 

 

	def solution(n, s):
	# 자연수 n개의 합으로 n보다 작은 s를 만들 수는 없으므로 [-1]을 리턴한다
	if n > s: return [-1]
	result = []
	# s를 n으로 나눈 몫이 n개이도록 초기값을 정한다.
	initial = s // n
	for _ in range(n):
	result.append(initial)
	idx = len(result) - 1
	# s를 n으로 나눈 몫에서 나머지만큼 각 값에 1씩 더해준다.
	for _ in range(s % n):
	result[idx] += 1
	idx -=1
	return result

view raw [프로그래머스] 최고의 집합.py hosted with ❤ by GitHub