[leetcode] Reducing Dishes

Reducing Dishes

나의 풀이

1에 들어오는 값이 0보다 클 때까지 계산해 주었다. 이렇게 계산하면 [음수 499개, 0이나 양수 1개]가 들어왔을 때 완전탐색 하는 거라서 O(N2)가 된다. 그래서 이렇게 안 하고 싶었는데 "언제 최댓값을 갖는 것인지 알 방법이 없는데 어쩌지🤔"하며 고민했다.

기존 코드

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sortedSatisfaction = sorted(satisfaction)
        index, sum, maxSum = 0, 0, 0
        isLast = False
        
        while True:
            startValue = sortedSatisfaction[index]
            if startValue > 0:
                isLast = True
            for start in range(index, len(sortedSatisfaction)):
                sum += sortedSatisfaction[start] * (start-index+1)
            maxSum = max(maxSum, sum)
            sum = 0
            index += 1
            if index > len(sortedSatisfaction)-1 or isLast:
                break
        
        return maxSum

다른 사람 풀이

최댓값이 되는 경우는 정렬된 satisfaction에서 큰 값을 기준으로 왼쪽으로 더하면서 음수가 나오는 경우 바로 앞이다. 그래서 오른쪽부터 왼쪽으로 값을 더해나가면서 음수가 나오는 경우가 있으면 그 지점 바로 앞에서부터 전체 만족도를 계산하면 된다. 이 방식은 시작하는 지점이 맨 왼쪽에 있다고 해도(예: [0,1,2, ...]) for문 한 번만 돌면 계산이 되기 때문에 O(N)에 해결된다.

어떻게 이걸 알게 되었는지는 정말 모르겠다. 코드를 여러 번 보다 보면 이런 것도 느낌적으로 알 수 있는 건가🫥

개선된 코드

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        sortedSatisfaction = sorted(satisfaction)
        start = len(sortedSatisfaction) - 1
        sum = 0
        
        for index in range(start, -1, -1):
            sum += sortedSatisfaction[index]
            if sum < 0:
                break
            start -= 1
        
        start += 1
        sum = 0
        
        for index in range(start, len(sortedSatisfaction)):
            sum += sortedSatisfaction[index] * (index-start+1)
        
        return sum

참고 자료

code Explainer