문제 설명
일정 수의 사탕을 한 줄로 선 n명의 사람들에게 아래와 같은 규칙으로 나눠주는 상황을 가정해 보겠습니다.
- 먼저 첫 번째 사람에게 사탕 1개, 두 번째 사람에게 2개를 주는 식으로 진행해 마지막(n번째) 사람에게 n개를 줍니다.
- 이후 다시 줄의 맨 앞으로 돌아가 첫 번째 사람에게 n+1개, 두 번째 사람에게 n+2개를 주는 식으로 마지막 사람에게 2×n개까지 나눠줍니다.
이 과정은 사탕이 모두 소진될 때까지 반복됩니다. 마지막 차례에는 남은 사탕 전부를 해당 사람에게 몰아주며, 이때 지급 개수가 반드시 직전보다 정확히 1개 많을 필요는 없습니다.
목표는 최종적으로 각 사람이 받은 사탕 개수를 담은 배열을 반환하는 것입니다. 예를 들어 사탕이 7개이고 n = 3이라면 결과는 [2, 2, 3]이 됩니다.
- 첫 번째 사람이 1개 수령 → [1, 0, 0]
- 두 번째 사람이 2개 수령 → [1, 2, 0]
- 세 번째 사람이 3개 수령 → [1, 2, 3]
- 다시 첫 번째 사람이 남은 1개 수령 → [2, 2, 3]
접근 방법
이 문제는 시뮬레이션으로 간단하게 해결할 수 있습니다. 단계는 다음과 같습니다.
- n개의 요소를 가진 배열 res를 만들고 0으로 초기화합니다.
- index를 0으로 설정합니다.
- candies가 0보다 큰 동안 아래 작업을 반복합니다.
- res[index mod n]에 candies와 index+1 중 작은 값을 더합니다.
- candies에서 실제로 지급한 개수(min(candies, index+1))만큼 뺍니다.
- index를 1 증가시킵니다.
- res를 반환합니다.
사탕 지급량이 1, 2, 3, …처럼 1씩 증가하므로 전체 반복 횟수 k는 대략 k(k+1)/2 ≤ candies를 만족합니다. 따라서 시간 복잡도는 O(√candies), 공간 복잡도는 O(n)입니다.
구현 예제
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
class Solution(object):
def distributeCandies(self, candies, num_people):
res = [0 for i in range(num_people)]
index = 0
while candies > 0:
res[index % num_people] += min(candies, index + 1)
candies -= (index + 1)
index += 1
return res
ob1 = Solution()
print(ob1.distributeCandies(8, 3))
입력
8 3
출력
[3, 2, 3]
사탕 8개를 3명에게 나누면 1, 2, 3개씩 한 바퀴 돈 뒤([1, 2, 3]) 남은 2개가 다시 첫 번째 사람에게 지급되어, 최종 결과는 [3, 2, 3]이 됩니다.