logoChat01.ai

class Solution { public: int findMaximizedCapi...

생성일: 2026년 5월 30일

답변에 사용된 모델 GPT-5.5 Thinking by Chat01

질문

class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
int n=profits.size();
vector<pair<int,int>> proj;
for(int i=0;i<n;i++){
proj.push_back({capital[i],profits[i]});
}
priority_queue<int> pq;
int idx=0;
int res=0;
while(k--){
while(idx<n){
if(proj[idx].first>w) break;
pq.push(proj[idx].second);
}
if(pq.empty()) return w;
w=w+pq.top();
pq.pop();
// k--;
}
return w;
}
}; fix this

사고

Thought for a couple of seconds

답변

You need to sort projects by required capital and increment idx inside the inner loop. Otherwise, idx never changes and the loop can become infinite.

cpp
class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();

        vector<pair<int, int>> proj;
        for (int i = 0; i < n; i++) {
            proj.push_back({capital[i], profits[i]});
        }

        sort(proj.begin(), proj.end());

        priority_queue<int> pq;
        int idx = 0;

        while (k--) {
            while (idx < n && proj[idx].first <= w) {
                pq.push(proj[idx].second);
                idx++;
            }

            if (pq.empty()) return w;

            w += pq.top();
            pq.pop();
        }

        return w;
    }
};

Main fixes:

cpp
sort(proj.begin(), proj.end());

and inside the inner loop:

cpp
idx++;

Without idx++, the same project keeps getting pushed forever.

질문

class Solution {
public:
struct cmp {
bool operator()(pair<int,int>& a, pair<int,int>& b) {
if(a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
};

text
int lastStoneWeight(vector<int>& stones) {
    unordered_map<int,int> f;
    int n=stones.size();
    priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> pq;
    for(int i=0;i<n;i++){
        f[stones[i]]++;
    }
    for(auto i:f){
        int key =i.first;
        int freq=i.second;
        pair<int,int> curr={key,freq};
        pq.push(curr);
    }
        while(pq.size()>1) {
        if(pq.top().second==1){
            int x=pq.top().first;
            pq.pop();
            if(pq.top().second==1){
                int y=pq.top().first;
                pq.pop();
                pq.push({x-y,1});
            }
            else{
                int z=pq.top().first;
              int c= pq.top().second-1;
              pq.pop();
              pq.push({z,c});
                pq.push({x-z,1});
            }
        }
        else{
            int m=pq.top().first;
           int l= pq.top().second;
           l--;
            if(l==1) pq.pop();
        }
    }
    if(pq.empty()) return 0;
    if(pq.top().second==0)  return 0;
    return pq.top().first;
}

}; fix this

사고

Thought for a couple of seconds

답변

Use a simple max-heap of stone weights. You do not need frequency pairs here.

cpp
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;

        for (int stone : stones) {
            pq.push(stone);
        }

        while (pq.size() > 1) {
            int x = pq.top();
            pq.pop();

            int y = pq.top();
            pq.pop();

            if (x != y) {
                pq.push(x - y);
            }
        }

        return pq.empty() ? 0 : pq.top();
    }
};

Why your code was breaking:

cpp
pq.push({x - y, 1});

can push 0, which should not be added.

Also here:

cpp
else {
    int m = pq.top().first;
    int l = pq.top().second;
    l--;
    if(l==1) pq.pop();
}

you reduce l, but you never update the heap with the new frequency. Also, when two equal stones are smashed, the frequency should decrease by 2, not 1.

The heap-only solution is the cleanest and accepted approach.

이 Q&A 공유하기