- Problem

1402. Reducing Dishes

- 내 풀이 (greedy, sorting)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        satisfaction.sort(reverse=True)

        if satisfaction[0] < 0:
            return 0

        total_sum = 0
        max_sum = 0

        for s in satisfaction:
            total_sum += s
            if total_sum < 0:
                break
            max_sum += total_sum

        return max_sum

- 결과

• 시간 복잡도: O(NlogN) (N: satisfaction의 길이)
• 공간 복잡도: O(1)