99클럽 코테 스터디 24일차 TIL, 프로그래머스 / IPO

 

https://leetcode.com/problems/ipo/

 

첫번째 풀이 : DFS

class Solution {
public:
    struct Project
    {
        int profit;
        int capital;

        bool operator < (const Project& project)
        {
            // return (capital - profit) > (project.capital - project.profit);
            return profit > project.profit;
        }
    };
    vector<bool>    visited;
    vector<Project> projects;
    int maxW = 0;

    void dfs(int curW, int accCnt, int maxCnt)
    {
        if (accCnt > maxCnt) return;

        // if (accCnt <= maxCnt)
        {
            maxW = max(maxW, curW);
            // return;
        }

        for (int idx = 0; idx < projects.size(); ++idx)
        {
            if (visited[idx]) continue;
            if (curW < projects[idx].capital) continue;
            int nxtW = curW;
            // nxtW -= projects[idx].capital;
            nxtW += projects[idx].profit;
            visited[idx] = true;
            dfs(nxtW, accCnt + 1, maxCnt);
            visited[idx] = false;
        }

    }

    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) 
    {
        // 일단, capital 기준으로 2차원 벡터를 만들어서, 그곳에 Project 들을 배치한다.
        // 그리고 profit 기준 내림차순 정렬을 한다.
        // 해당 project 를 선택후 w 를 update 해가는 것이다.
        int cnt = 0, curW = w;
        visited.resize(profits.size());

        for (int idx = 0; idx < profits.size(); ++idx)
            visited[idx] = false;
        for (int idx = 0; idx < profits.size(); ++idx)
            projects.push_back({profits[idx], capital[idx]});

        dfs(w, 0, k);

        return maxW;
    }
};

처음 시도는 시간 초과가 발생했다.

단순 그래프 문제는 아닌 것 같다.

 

사실 맨 처음에는 냅색 알고리즘으라고 생각했으나

w 값이 계속 바뀔 수도 있다는 점에서, 전형적인 냅색은 아니라고 생각했다.

 

그렇다면 "그리디" 문제 라고 생각된다.

정렬을 어떻게 해야 하나라고 생각하기도 했다.

 

두번째 풀이 : Heap 활용 (우선순위 큐)

 

class Solution {
public:
    struct ProfitStruct
    {
        int profit; // max heap
        int index;

        bool operator < (const ProfitStruct& project) const
        {
            return profit < project.profit;
        }
    };

    struct CapitalStruct
    {
        int capital;    // min heap
        int index;

        bool operator < (const CapitalStruct& project) const
        {
            return capital > project.capital;
        }
    };

    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) 
    {
        priority_queue<CapitalStruct>   minCapitalHeap;
        priority_queue<ProfitStruct>    maxProfitHeap;
        int cnt = 0;

        for (int idx = 0; idx < profits.size(); ++idx)
            minCapitalHeap.push(CapitalStruct(capital[idx], idx));

        while(cnt < k)
        {
            while(!minCapitalHeap.empty() && minCapitalHeap.top().capital <= w)
            {
                int idx = minCapitalHeap.top().index;
                maxProfitHeap.push(ProfitStruct(profits[idx], idx));
                minCapitalHeap.pop();
            }

            if (maxProfitHeap.empty()) break;

            w += maxProfitHeap.top().profit;
            maxProfitHeap.pop();
            cnt += 1;
        }

        // profit 기반 max heap
        // -> 
        // capital 기반 min heap
        // -> 

        // 일단 min heap 으로 모든 녀석이 들어가 있다.
        // 일단 현재 w 보다 min heap 에서 꺼낸 애가 capital 이 작거나 같으면
        // profit 기반 max heap 에 push 한다.
        // 자. 그러다가, capital 이 더 w 보다 크면. 이제 그만 pop

        // 자. 이제 profit 기반 max heap 에서 최고 profit 을 꺼낸다.
        // 그리고 w 를 update
        // 이제 또 다시 min heap 에서 pop

        return w;
    }
};