23.03.29. 풀었던 문제들

Leetcode 1402. Reducing Dishes

Intuition

 문제를 보고, 일단 정렬한 후 뽑기 시작할 시작지점을 고르면 될 것이라 생각했다.

 오름차순 정렬되어 있는 상태에서, 제일 끝 index i를 시작지점으로 여기고 여기부터 시작한다.(제일 끝 index가 제일 큰 값이므로) 이 때, i가 한 칸 앞으로 당겨지면 총 계에 arr[i-1] + arr[i] + ... + arr[n-1]이 더해져야 한다. 이 값을 sum이라고 할 때 sum이 0보다 크다면 i를 한 칸 앞으로 당겨 sum을 maximize할 수 있다. 그러면 sum이 0보다 크면 이것을 반복하면 된다.

 arr[i-1] + ... + arr[n-1]은 prefix sum으로 쉽게 구할 수 있다. 따라서 O(n)으로 풀리는 문제이다.

 

Solution

 intuition에서는 오름차순 정렬되어 있는 상태에서 psum을 사용했다. 그러나 이렇게 말고, 내림차순 정렬되어 있는 상태로 시작하면 arr[0] + ... + arr[i]가 되므로, prefix sum을 사용할 필요가 없다. 앞에서부터 더해주면 되기 때문이다. 마찬가지로 이 값이 0보다 크면 i를 한 칸 더 전진시키면 된다.

// Runtime 0 ms Beats 100%
// Memory 8 MB Beats 98.26%

class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int n = satisfaction.size();
        sort(satisfaction.begin(), satisfaction.end(), greater<int>());

        int sum = 0, idx = -1; // *** 실수 : idx가 없을 때 값이 들어가지 않을 수 있었음.
        // i 값을 구함. arr[0] + ... + arr[i]가 0보다 크면 전진시키도 i를 기억함.
        for(int i = 0; i<n; i++){
            if(sum + satisfaction[i] < 0) break;
            sum += satisfaction[i];
            idx = i;
        }
        
        // 그 i가 optimization value이다. 이 값으로 정답 계산.
        sum = 0;
        for(int i = idx, cnt = 1; i>=0; i--, cnt++){
            sum += satisfaction[i] * cnt;
        }
        return sum;
    }
};

 

시간복잡도

 앞에서부터 제일 뒤까지 순회를 2번 하므로 O(n), 정렬에 O(nlogn)이다.

 

공간복잡도

 주어진 공간 외에 별다른 array를 사용하지 않는다. O(1).

 

후기

 오랜만에 beats 100%다. 기분이 좋군.