23.02.23. 풀었던 문제들

리트코드 daily challenge - 502. IPO

 오늘의 daily challenge는 hard 문제였다. 아직 medium도 시작하지 못했는데 어떻게 풀지..? 좀 막막했는데 문제를 읽다 보니 그리 어려운 것은 아니었다.

 문제 조건은 k개의 프로젝트를 끝낼 수 있고, total capital를 최대화 하는 것이다. 초기 자본은 w이고 profit[i] : 순수익,
capital[i] : 시작하기 위한 자본이다.

 문제 제한 조건을 보았을 때 nlogn으로 풀어야 되는 문제같다. 최대한 naive하게 접근해 보자.

 

• 매 탐색 시 현재 w보다 작은 capitals 중 profit이 제일 큰 것을 빼내야 한다. (erase) 만약 profit이 같다면 capital이 작은 것을 빼내야 할 것이다.
  • 모든 값이 0보다 크거나 같음을 보장받기 때문에 w는 monotonic increasing이다. capital가 오름차순 정렬되어 있다고 생각하면 w의 upper bound를 logn에 구할 수 있다.
  • 직전까지 탐색했던 index(previdx)부터 upper bound index -1까지 pq에 넣고, previdx를 갱신한다.
    • pq는 profit이 제일 큰 것이 top에 있다. 만약 profit이 같다면 capital이 작은 것이 top에 있다.

 

 이렇게 접근하면, binary search 하나와 pq 하나로 문제를 풀 수 있을 것 같다! 그러면 결국 구현 문제다. 

 

 실수했던 부분은

• pq 정렬할 때 last index 원하는 조건으로 오게 정렬해야 한다. 거꾸로 정렬해서 디버깅을 했다.
• indexing에 유의하자.

 

 time complexity는, O(nlogn)이다.

• 정렬에 O(nlogn)이 걸린다.
• while문은 O(nlogn)이다.
  • 각 binary search에서 O(logn)이다. worst case n번 binary search하므로 O(nlogn)이다.
  • pq push할 때 O(logn)이다. worst case n번 push하므로 O(nlogn)이다.
  • pq pop은 O(1)이다.
• 따라서 O(nlogn)이다.

 

 space complexity는, O(N)이다.

• 새 vector 선언에 O(N), pq에 worst N개가 들어간다.

 

 이렇게 완성된 코드는 아래와 같다. 코드를 쓰고, 디버깅을 하고 예제를 통과하는 것을 확인했고 이게 답인 것을 확신했다. 두근두근거린다. 재밌다!

// runtime: 327ms (beats 22.75%)
// memory 80.3MB (beats 77.58%)

struct project{
    int profit, capital;
};

bool cmp(project &a, project &b){
        if(a.capital == b.capital){
            return a.profit < b.profit;
        }
        return a.capital < b.capital;
}

// get largest profit. if same profit, then get smaller capital
struct pqcmp{
    bool operator() (project &a, project &b) const{
        if(a.profit == b.profit){
            return a.capital > b.capital; // 실수 : 값을 거꾸로 넣음 
        }
        else return a.profit < b.profit;
    }
};

class Solution {
public:
    int getUpperBound(int weight, vector<project>& projects){
        int start = 0, end = projects.size();
        int mid;
        while(start < end){
            mid = start + (end - start) / 2;
            if(projects[mid].capital > weight){ // must search forward
                end = mid; // 기억하자! 앞를 먼저 탐색하자.
            }
            else{ // must search forward
                start = mid + 1; // 기억하자 : start는 항상 mid + 1이다.
            }
        }
        return end;
    }
    
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capitals) {
        int n = profits.size();
        
        // initialize projects
        vector<project> projects(n); // .first : profit, .second : capital
        for(int i = 0; i<n; i++){
            projects[i].profit = profits[i];
            projects[i].capital = capitals[i];
        }
        sort(projects.begin(), projects.end(), cmp); // order by ascending capital

        int answer = 0, previdx = 0; // 실수 : previdx를 0부터, ubidx-1까지 탐색해야 했다. indexing에 유의하자.
        priority_queue<project, vector<project>, pqcmp> pq;
        while(k--){
            // get upper bound of w
            int ubidx = getUpperBound(w, projects);
            for(int i = previdx; i<ubidx; i++){ // insert on pq
                pq.push(projects[i]);
            }
            previdx = ubidx; // update previdx

            // get largest profit
            if(!pq.empty()){
                w += pq.top().profit;
                pq.pop();
            }
            // return w
            
        }
        return w;
    }
};

 

 이제 이걸 어떻게 개선해야 할까... 답안을 봤다. 어? binary search를 쓸 필요가 없다. previdx를 저장하고, previdx++을 해가면서 projects[previdx] <= w로 반복문을 돌리면, previdx부터 upper bound-1까지 들어간다. 엄...

        while(k--){
            // here: 굳이 binary search를 쓸 필요가 없네?
            // int ubidx = getUpperBound(w, projects, previdx);
            // for(int i = previdx; i<ubidx; i++){ // insert on pq
            //     pq.push(projects[i]);
            // }
            // previdx = ubidx; // update previdx

            // push all projects to pq which its capital is less than w.
            // this can be linear, cause projects vector is sored by capital ascending.
            while(previdx < n && projects[previdx].capital <= w){
                pq.push(projects[previdx]);
                previdx++;
            }

            // get largest profit
            if(!pq.empty()){
                w += pq.top().profit;
                pq.pop();
            }
            else return w;
            
        }