[C++][leetcode] Last Stone Weight :: seoftware

 

---

 

소스코드

---

 

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        if(stones.empty()) return 0;
        priority_queue<int, vector<int>, less<int>> pq;
        for(int i = 0; i<stones.size(); i++){
            pq.push(stones[i]);
        }
        while(pq.size() > 1) {
            int first = pq.top(); pq.pop();
            int second = pq.top(); pq.pop();
            if(first != second) pq.push(first-second);
        }
        return pq.size()==1?pq.top():0;
    }
};

 

1. 우선순위 큐 priority queue 를 사용해서 풀었다. pq를 사용하지 않고 while문 돌 때마다 sort를 수행해도 될 것 같다.

2. pq에 내림차순으로 stones에 있는 원소들을 넣는다.

3. pq의 앞에 두 원소(가장 큰 원소 두 개)를 꺼내서 값이 서로 다르면 차를 다시 pq에 넣어주고, 같으면 무시한다.

4. while문이 끝나면 pq에는 원소가 하나 남거나 아예 남지 않게 된다. 하나 남으면 그것을 반환하고 아니면 0을 반환한다.