99클럽 코테 스터디 23일차 TIL + Java Algorithm

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• LeetCode - IPO (문제 링크)
• 우선순위 큐

 

---

 

문제 설명

LeetCode는 IPO(Initial Public Offering) 전에 자본을 최대한 늘리기 위해 여러 프로젝트를 진행하려고 합니다. 하지만 자원은 제한적이므로, IPO 전에 최대 k개의 프로젝트만 진행할 수 있습니다.

초기 자본 w와 각 프로젝트의 순수 이익(profits[i]) 및 시작하기 위한 최소 자본(capital[i])이 주어졌을 때, 최대 k개의 프로젝트를 선택하여 최종 자본을 최대화하는 방법을 찾아야 합니다.

제약사항

• 1 ≤ k ≤ 105
• 0 ≤ w ≤ 109
• n == profits.length
• n == capital.length
• 1 ≤ n ≤ 105
• 0 ≤ profits[i] ≤ 104
• 0 ≤ capital[i] ≤ 109

입출력 예

예제 1:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

예제 2:

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6

 

---

 

문제 접근

이 문제는 주어진 자본으로 시작할 수 있는 프로젝트 중에서 가장 큰 이익을 얻는 프로젝트를 선택하여 최종 자본을 최대화하는 방법을 찾는 문제입니다. 이때, 두 개의 우선순위 큐를 사용하여 자본 조건에 맞는 프로젝트 중 가장 큰 이익을 얻을 수 있는 프로젝트를 효율적으로 선택하는 방식을 사용합니다.

1. 프로젝트 초기화
   • 모든 프로젝트를 자본 기준으로 오름차순 정렬된 큐에 저장합니다.
2. 프로젝트 선택
   • 현재 자본으로 시작할 수 있는 모든 프로젝트를 이익 기준으로 내림차순 정렬된 큐에 넣습니다.
   • 가장 이익이 큰 프로젝트를 선택해 자본을 증가시킵니다.
3. 최종 자본 계산
   • 최대 k개의 프로젝트를 선택한 후, 최종 자본을 반환합니다.

 

풀이

import java.util.PriorityQueue;

class Solution {

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // 자본이 적은 순으로 프로젝트를 저장하는 우선순위 큐
        PriorityQueue<Project> minCapitalHeap = new PriorityQueue<>((a, b) -> a.cost - b.cost);
        // 이익이 큰 순으로 프로젝트를 저장하는 우선순위 큐
        PriorityQueue<Project> maxProfitHeap = new PriorityQueue<>((a, b) -> b.profit - a.profit);

        // 모든 프로젝트를 자본 기준으로 정렬된 큐에 추가
        for (int i = 0; i < profits.length; i++) {
            minCapitalHeap.offer(new Project(profits[i], capital[i]));
        }

        // 최대 k개의 프로젝트 선택
        for (int i = 0; i < k; i++) {
            // 현재 자본으로 수행 가능한 모든 프로젝트를 이익 기준으로 정렬된 큐에 추가
            while (!minCapitalHeap.isEmpty() && minCapitalHeap.peek().cost <= w) {
                maxProfitHeap.offer(minCapitalHeap.poll());
            }

            // 수행 가능한 프로젝트가 없으면 종료
            if (maxProfitHeap.isEmpty()) {
                break;
            }

            // 가장 큰 이익을 얻을 수 있는 프로젝트를 선택
            w += maxProfitHeap.poll().profit;
        }

        return w;
    }

    private class Project {
        int profit;
        int cost;

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

 

풀이 설명

1. 프로젝트 초기화
   • 모든 프로젝트를 자본이 적은 순으로 정렬하여 minCapitalHeap 우선순위 큐에 저장합니다.
   • 각 프로젝트는 이익과 시작 비용을 포함하는 객체로 관리됩니다.
2. 프로젝트 선택
   • 최대 k번의 반복을 통해, 현재 자본으로 시작할 수 있는 모든 프로젝트를 maxProfitHeap에 추가합니다. 이 큐는 이익이 큰 순서대로 정렬됩니다.
   • maxProfitHeap에서 가장 큰 이익을 얻을 수 있는 프로젝트를 선택하여 자본을 증가시킵니다.
3. 최종 자본 계산
   • 최대 k개의 프로젝트를 선택한 후, 최종 자본을 반환하여 문제에서 요구하는 최댓값을 구합니다.

 

---

 

마무리하며

• 이번 문제를 통해 그리디 알고리즘과 우선순위 큐를 활용하여 최적의 선택을 반복하는 방식으로 문제를 해결하는 방법을 학습했습니다.
• 최적의 선택을 두개의 우선순위 큐를 활용하는 방법으로 문제를 해결했습니다.