99클럽 코테 스터디 23일차 TIL / [LeetCode] IPO

오늘의 학습 키워드

---

그리디, PriorityQueue

문제

---

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

• 플랫폼: LeetCode
• 문제명: IPO
• 난이도: Hard

풀이

---

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue<Project> capitalPQ = new PriorityQueue<>((p1, p2) -> p1.capital - p2.capital);
        PriorityQueue<Project> profitPQ = new PriorityQueue<>((p1, p2) -> p2.profit - p1.profit);

        for(int i=0; i<profits.length; i++) {
            capitalPQ.offer(new Project(profits[i], capital[i]));
        }

        for(int i=0; i<k; i++) {
            while(!capitalPQ.isEmpty() && capitalPQ.peek().capital <= w) {
                profitPQ.offer(capitalPQ.poll());
            }

            if(profitPQ.isEmpty()) {
                break;
            }

            w += profitPQ.poll().profit;
        }

        return w;
    }

    static class Project {
        int profit;
        int capital;

        public Project(int profit, int capital) {
            this.profit = profit;
            this.capital = capital;
        }
    }
}

접근

• 현재 가지고 있는 자본(=w)으로 수행할 수 있는 프로젝트 중 가장 profit이 높은 프로젝트를 그리디하게 구현하는 문제였습니다.
• 접근
  • w는 프로젝트를 진행함에 따라 계속 증가하는 특징을 가집니다.
  • 따라서, 최소 힙의 형태를 갖는 capitalPQ와 최대 힙을 갖는 profitPQ를 만들고 w로 수행할 수 있는 프로젝트들은 profitPQ에 저장한 뒤 가장 profit이 높은 프로젝트들을 꺼내는 방식으로 구현할 수 있습니다.
• 구현

  • 최소 힙에 모든 capital 값들을 저장합니다.

    for(int i=0; i<profits.length; i++) {
        capitalPQ.offer(new Project(profits[i], capital[i]));
    }

  • 이후 k번만큼 for문을 돌면서

    1. 현재 w로 수행 가능한 프로젝트를 profitPQ에 저장

       while(!capitalPQ.isEmpty() && capitalPQ.peek().capital <= w) {
           profitPQ.offer(capitalPQ.poll());
       }

    2. 수행 가능한 프로젝트가 저장된 profitPQ에서 가장 높은 profit을 갖는 프로젝트 수행

       w += profitPQ.poll().profit;

소요 시간

1시간 30분