99클럽 코테 스터디 23일차 TIL + IPO (java)

 

💡 문제

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

권장 시간

• 1시간

소요 시간

• 1시간 40분 + a

나의 풀이 코드

import java.util.*;

class Solution {
    private class Project {
        int capital;
        int profit;

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

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {

        ArrayList<Project> projects = new ArrayList<>();
        for (int i = 0; i < profits.length; i++) {
            projects.add(new Project(capital[i], profits[i]));
        }

        // capital이 적게 드는 순서로 정렬
        Collections.sort(projects, (o1, o2) -> o1.capital - o2.capital);

        // 최대힙 설정
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);

        // 최대 k개 프로젝트 선택 -> k번 뽑기
        int idx = 0;
        for (int i = 0; i < k; i++) {
            // 현재 capital보다 작거나 같으면 모든 프로젝트를 큐에 추가
            while (idx < capital.length && projects.get(idx).capital <= w) {
                pq.add(projects.get(idx).profit);
                idx++;
            }

            // 실행 가능한 프로젝트가 없으면 break
            if (pq.isEmpty()) {
                break;
            }

            // 가장 큰 profit 선택
            w += pq.poll();
        }

        return w;
    }
}

주요사항

0번 idx를 탐색하고 그 이후에는 1번 idx부터 탐색하도록 해야됐는데.. 방법을 몰라서 시간을 많이 보냈다. 투포인터까지 해봤는데 도저히 안됐음 ..

Priority Queue로 풀 생각은 상상도 못했다.