23.04.24. 풀었던 문제들

Leetcode 1046. Last Stone Weight

 PQ를 이용하면 쉽게 풀 수 있는 문제. 딱히 설명할 거리도 없다,,,

// Runtime 0 ms Beats 100%
// Memory 7.7 MB Beats 41.71%

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int, vector<int>, less<int>> pq;
        for(int stone : stones) pq.push(stone);

        while(pq.size() > 1){
            int f = pq.top(); pq.pop();
            int s = pq.top(); pq.pop();
            if(f != s) pq.push(abs(f - s));
        }

        if(pq.empty()) return 0;
        return pq.top(); // *** 실수 : 종료조건
    }
};

 

시간복잡도

 stones size를 n이라고 하면 pq에 n번의 insert, worst case n번의 pop이 있으므로 O(nlogn)이다.

 

공간복잡도

 pq, stones에 O(n)만큼 사용하므로 O(n)