99클럽 코테 스터디 23일차 TIL / IPO(Leetcode)

 

오늘의 학습 키워드

   - 알고리즘

   - 그리디

   - DP

 

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

 

풀이는 다음과 같다.

import java.util.*;

class Solution {

    class Node {
        int profit, capital;
        Node(int _profit, int _capital) {
            profit = _profit; capital = _capital;
        }
    }
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        
        int n = profits.length;

        ArrayList<Node> nodeList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nodeList.add(new Node(profits[i], capital[i]));
        }
        nodeList.sort((o1, o2) -> o1.capital - o2.capital);

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        int profitSum = w, j = 0;
        
        for (int i = 0; i < k; i++) {
            while (j < n && nodeList.get(j).capital <= profitSum) {
                pq.add(nodeList.get(j).profit);
                j++;
            }

            if (pq.isEmpty()) break;

            profitSum += pq.poll();
        }

        return profitSum;
    }
}