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

오늘의 학습 키워드

• 그리디 알고리즘
• 우선순위 큐
• 정렬

문제 이해

이 문제는 초기 자본 w와 각 프로젝트의 이익 profits, 그리고 해당 프로젝트를 시작하는 데 필요한 자본 capital이 주어질 때, k번의 투자 기회를 활용해 최대 자본을 얻는 문제입니다. 목표는 가능한 자본 범위 내에서 최대 이익을 가져오는 프로젝트를 선택해 자본을 최대로 증가시키는 것입니다.

나의 풀이

package org.example.ipo;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        int k = 3;
        int w = 0;
        int[] profits = new int[]{1, 2, 3};
        int[] capital = new int[]{0, 1, 1};

        System.out.println(findMaximizedCapital(k, w, profits, capital));
    }

    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];

        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }

        // 자본을 기준으로 오름차순 정렬
        Arrays.sort(projects, (a, b) -> a[0] - b[0]);

        // 이익을 기준으로 내림차순 정렬하는 우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        int i = 0;
        while(k-- > 0){
            // 현재 자본으로 수행 가능한 모든 프로젝트를 우선순위 큐에 넣음
            while(i < n && projects[i][0] <= w){
                pq.offer(projects[i][1]); // 가능한 이익을 큐에 추가
                i++;
            }

            if(!pq.isEmpty()){
                w += pq.poll(); // 가장 큰 이익을 얻는 프로젝트 선택
            } else {
                break; // 더 이상 수행할 수 있는 프로젝트가 없으면 종료
            }
        }
        return w;
    }
}

풀이 설명

1. 프로젝트 데이터 초기화

   • 각 프로젝트는 필요한 자본과 이익을 쌍으로 가지며, 이를 projects 배열에 저장합니다.
   • 프로젝트 배열을 자본을 기준으로 오름차순으로 정렬하여, 자본이 적게 필요한 프로젝트부터 처리할 수 있도록 합니다.

2. 우선순위 큐를 사용한 최대 이익 선택

   • 가능한 프로젝트 중에서 가장 이익이 큰 프로젝트를 선택하기 위해 우선순위 큐(Priority Queue)를 사용합니다. 큐는 이익을 기준으로 내림차순 정렬되며, 현재 자본으로 수행할 수 있는 프로젝트만 큐에 추가됩니다.
   • k번의 기회를 주어진 만큼 반복하며, 각 반복에서 수행할 수 있는 모든 프로젝트를 큐에 넣습니다.
   • 큐에서 가장 이익이 큰 프로젝트를 선택해 자본을 증가시키고, 그 자본으로 다시 수행 가능한 프로젝트를 큐에 추가하는 방식으로 진행합니다.

3. 최종 자본 반환

   • k번의 투자가 끝나거나 더 이상 수행할 수 있는 프로젝트가 없을 때, 최종 자본 w를 반환합니다.

예제

주어진 예제에서:

• 초기 자본 w = 0, 최대 k = 3번의 투자 기회
• 프로젝트 1: 자본 0, 이익 1
• 프로젝트 2: 자본 1, 이익 2
• 프로젝트 3: 자본 1, 이익 3

투자 시나리오:

1. 자본이 0인 프로젝트 1을 선택하여 이익 1을 얻고, 자본 w는 1이 됩니다.
2. 자본이 1인 프로젝트 3을 선택하여 이익 3을 얻고, 자본 w는 4가 됩니다.
3. 마지막으로 자본이 1인 프로젝트 2를 선택하여 이익 2를 얻고, 최종 자본 w는 6이 됩니다.