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

 

- 오늘의 학습 키워드 : PriorityQueue

[문제 이름 :   IPO (LeetCode - 502번 문제, Hard) ]

문제 url : https://leetcode.com/problems/ipo/

 

 

내가 작성한 코드는 아래와 같다.

import java.util.*;
public class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        Capital[] projects = new Capital[profits.length];
        for(int i=0; i<profits.length; i++) {
            projects[i] = new Capital(capital[i], profits[i]);
        }

        Arrays.sort(projects);
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        int index = 0;
        int answer = w;

        for(int i=0; i<k; i++) {
            while(index < profits.length && projects[index].capital <= answer) {
                pq.add(projects[index++].profit);
            }

            if(pq.isEmpty()) {
                break;
            }
            answer += pq.poll();
        }
        return answer;
    }

    static class Capital implements Comparable<Capital> {
        int capital;
        int profit;

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

        @Override
        public int compareTo(Capital c) {
            return this.capital - c.capital;
        }
    }
}

[풀이 과정]

1. 자본 순으로 오름차순 시킨다.

2. PriorityQueue에는 큰 수익을 내는 것을 기반으로 내림차순 하면서, 구하고자 하는 answer에 더해준다.             while(index < profits.length && projects[index].capital <= answer) {
                pq.add(projects[index++].profit);
            }
이 부분의 코드가 생각해내기 어려웠을 것 같다. 좀 더 직관적으로 쉽게 풀이한다면, 아래 적어논 코드처럼 풀이하는 것이 훨씬 수월할 것 같다.

풀이 시간 : 2시간
시간복잡도가 터져서, 다른 분의 블로그를 참고하여 이해 후, TIL을 작성하였다.

[참고]

https://leetcode.com/problems/ipo/solutions/3220203/java-solution/

두 개 PriorityQueue로 풀이 : https://walkccc.me/LeetCode/problems/502/#__tabbed_1_2

코드 로직은 동일하지만, 두 개의 PriorityQueue를 사용해서 풀이 한 방법도 있었다.

* 두 개의 PriorityQueue로 풀이하기

class Solution {
  public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
    Queue<Capital> minHeap = new PriorityQueue<>((a, b) -> a.cap - b.cap);
    Queue<Capital> maxHeap = new PriorityQueue<>((a, b) -> b.pro - a.pro);

    for (int i = 0; i < Capital.length; ++i)
      minHeap.offer(new T(Profits[i], Capital[i]));

    while (k-- > 0) {
      while (!minHeap.isEmpty() && minHeap.peek().cap <= W)
        maxHeap.offer(minHeap.poll());
      if (maxHeap.isEmpty())
        break;
      W += maxHeap.poll().pro;
    }

    return W;
  }
  
  static class Capital {
  public int pro;
  public int cap;
  public Capital(int pro, int cap) {
    this.pro = pro;
    this.cap = cap;
  }
}
}

로직을 잘 살펴보면 위 코드와 동일하다는 것을 알 수 있다.

 

 

내일은 Deque 알고리즘에 대해 복습하고, 추가로 Map을 활용하는 문제를 풀이해보려고 한다.

502. IPO - LeetCode Solutions